PureBasic Forums - English

Posted: **Sun Jun 24, 2007 3:06 am**

Hi Michael,

My function for checking palindromes seems to be very slightly quicker than yours.

Running the following code on my system I get an average time of 197.500ms for your routine and 186.110ms for mine.

Code: Select all

; Project Euler - Problem 4
;
; A palindromic Number reads the same both ways. the largest palindrome made
; from the product of two 2-digit numbers is 9009 = 91 × 99.
;
; Find the largest palindrome made from the product of two 3-digit numbers.

#LoopTimes = 100

;- Using Michael Vogel's palindrome routine

Procedure.l MichaelsPalindrome(x.s)
  Protected l=Len(x)-1 
  Protected i=l>>1 
  While i>=0 
    If PeekB(@x+i)<>PeekB(@x+l-i) 
      ProcedureReturn #False 
    EndIf 
    i-1 
  Wend 
  ProcedureReturn #True 
EndProcedure

TimeStart = GetTickCount_()

For loop = 1 To #LoopTimes
  
  MichaelsResult = 0
  For a = 100 To 999
    For b = 100 To 999
      Product = a * b
      If MichaelsPalindrome(Str(Product))
        If Product > MichaelsResult
          MichaelsResult = Product
        EndIf
      EndIf
    Next
  Next
  
Next

MichaelsTimeElapsed = GetTickCount_() - TimeStart

;- Using my palindrome routine

Procedure MyPalindrome(A$)
  
  Protected i, length = Len(A$) - 1
  
  For i = 0 To length
    If PeekB(@A$ + i) <> PeekB(@A$ + length - i)
      ProcedureReturn 0
    EndIf
  Next
  
  ProcedureReturn 1
  
EndProcedure

TimeStart = GetTickCount_()

For loop = 1 To #LoopTimes
  
  MyResult = 0
  For a = 100 To 999
    For b = 100 To 999
      Product = a * b
      If MyPalindrome(Str(Product))
        If Product > MyResult
          MyResult = Product
        EndIf
      EndIf
    Next
  Next
  
Next

MyTimeElapsed = GetTickCount_() - TimeStart

;- Display information

Text$ = "Average time elapsed for Michael's routine: " + StrF(MichaelsTimeElapsed / #LoopTimes, 3)+"ms (Result: " + Str(MichaelsResult) + ")" + Chr(10)
Text$ + "Average time elapsed for my routine: "+StrF(MyTimeElapsed / #LoopTimes, 3)+"ms (Result: " + Str(MyResult) + ")"

MessageRequester("Palindrome Comparison", Text$)

Kind regards,

Francis.

Posted: **Sun Jun 24, 2007 5:40 pm**

@Dreamland Fantasy,

Here is a different approach to problem 4 that will speed up your solution 1000 times. or in other words make your average time 1.86110 ms.

Change your code(s) from:

Code: Select all

or loop = 1 To #LoopTimes
 
  MyResult = 0
  For a = 100 To 999
    For b = 100 To 999
      Product = a * b
      If MyPalindrome(Str(Product))
        If Product > MyResult
          MyResult = Product
        EndIf
      EndIf
    Next
  Next
 
Next

to:

Code: Select all

For loop = 1 To #LoopTimes
  a2=100
  MyResult = 0
  For a = 999 To a2 Step -1
    b1=a:b2=a2
    For b = b1 To b2 Step -1
      Product = a * b
      If MyPalindrome(Str(Product))
        If Product > MyResult
          MyResult = Product
          a2=b+1
          If a2>a
            Break 2
          EndIf
          Break
        EndIf
      EndIf
    Next
  Next
  
Next

You thought the challenge was merely to find the highest of all palindromes that were the result of two 3-digit factors, instead you should have been searching for the highest factors that would produce a palindrome. My modification eliminates the wasteful searching of all the possible products from the factors by doing 3 things:

1. Start with the highest factors and work towards the smallest ones.
2. Only check half the products. (i.e 333*555 is the same as 555*333)
3. If a product is a palindrome only look for a palindrome among higher products from then on (limit the range).

This is the first time I have joined this disucussion. I hope I understood the problem correctly. If I misunderstood then my solution is probably not valid. Oops!

Posted: **Sun Jun 24, 2007 6:19 pm**

Hi Demivec,

Thanks for the input!

The main loop I posted was more to illustrate the actual speed of the Palindrome() routine rather than the speed of the main loop which re-reading my post probably wasn't clear.

As it stands I felt that the calculation time was satisfactory since it is completed in under a second. That said, the only optimisation I made in my 'final' version was to limit the range from 900 to 999 rather than 100 to 999.

The techniques you suggested (plus a few others) I have already used in some of the other problems where if I was doing it by brute force method would take far too long.

Kind regards,

Francis.

Posted: **Sun Jun 24, 2007 6:34 pm**

Hi Demivec,

Looking at your solution I noticed an obvious optimisation. Try this code:

Code: Select all

For loop = 1 To #LoopTimes 
  a2=100 
  MyResult = 0 
  For a = 999 To a2 Step -1 
    b1=a:b2=a2 
    For b = b1 To b2 Step -1 
      Product = a * b 
      If Product > MyResult 
        If MyPalindrome(Str(Product)) 
          MyResult = Product 
          a2=b+1 
          If a2>a 
            Break 2 
          EndIf 
          Break 
        EndIf 
      EndIf 
    Next 
  Next 
  
Next

All I have done is swapped two of the lines with If statements around so that you are performing less palindrome checks. With your code it took an average time of 2.262ms and with the modification it took 1.654ms.

Kind regards,

Francis.

Posted: **Sun Jun 24, 2007 8:43 pm**

Hi Demivec,

I've simplified your code a bit to make it slightly faster.

Code: Select all

For loop = 1 To #LoopTimes
  
  min = 100
  MyResult = 0
  For a = 999 To min Step -1
    For b = a To min Step -1
      Product = a * b
      If Product > Result
        If MyPalindrome(Str(Product))
          MyResult = Product
          min = b + 1
          If min > a
            Break 2
          EndIf
          Break
        EndIf
      EndIf
    Next
  Next
  
Next

The average time now has been reduced to 1.560ms.

Kind regards,

Francis.

Posted: **Sun Jun 24, 2007 9:38 pm**

Dreamland Fantasy wrote:That said, the only optimisation I made in my 'final' version was to limit the range from 900 to 999 rather than 100 to 999

I think you can only use that range limitation if you already knew what the answer was. That's why I included the full range of unique factors.

Dreamland Fantasy wrote:The average time now has been reduced to 1.560ms.

Fast!

Posted: **Mon Jun 25, 2007 1:27 am**

Demivec wrote:I think you can only use that range limitation if you already knew what the answer was. That's why I included the full range of unique factors.

I assumed that there would be a good chance that the answer would be produced by this range of numbers which is why they were chosen. This was supported by the fact that the answer I got was the same as the one expected on the Project Euler website.

If the answer turned out to be wrong I would have expanded the range.

Kind regards,

Francis.

Posted: **Mon Jun 25, 2007 7:20 am**

Dreamland Fantasy wrote: Hi Michael,
My function for checking palindromes seems to be very slightly quicker than yours. [...]

Hi Francis,

interesting that your routine is faster, I see only two differences:
o it starts "searching" from the beginning - my procedure starts from the middle
o it checks the whole string (if it is a palindrom) - my procedure checks only "the half" of the string

So yours should be faster, when...
o there are few palindromes and the difference will be at the edge

...and my procedure should be faster, when...
o there are many palindromes or the differences will be in the middle

But it demonstrates, that even small changes are able to influence the running time :roll:

Michael

Btw, I need someone to "tune" my code for problem 110 which actually would run for years (!) until I'll get a result...

Posted: **Mon Jun 25, 2007 10:12 am**

Hi Michael,

Even more interesting, I have just tried the code to compare palindromes on another computer. Sometimes your code is faster, sometimes mine is faster and sometimes they're neck and neck.

Problem 110 does look a doozy

, but I'm not even at that stage yet. The highest problem I've done so far is 56, but I've got a lot of gaps to fill in below that.

Kind regards,

Francis.

Posted: **Mon Jun 25, 2007 11:03 am**

Michael Vogel wrote:Btw, I need someone to "tune" my code for problem 110 which actually would run for years (!) until I'll get a result...

I haven't tried 110 or 108 which is the easier version, but one thing I did notice is that n seems to be a factor of x * y (based on the information provided in problem 108, I haven't checked any further than this). I don't know if you could use this to simplify things.

Kind regards,

Francis.

Posted: **Tue Jun 26, 2007 11:52 am**

Dreamland Fantasy wrote: I haven't tried 110 or 108 which is the easier version, but one thing I did notice is that n seems to be a factor of x * y (based on the information provided in problem 108, I haven't checked any further than this). I don't know if you could use this to simplify things.

Kind regards,

Francis.

Thanks Francis, yes there's something like 2*3*5*7*11*... which makes 108 not that complicate (but tricky enough;), but 110 is even worse! And it's the only "X" in my completion list (http://projecteuler.net/index.php?secti ... file=11160) for now

Posted: **Tue Jun 26, 2007 12:09 pm**

Michael Vogel wrote:
Dreamland Fantasy wrote: I haven't tried 110 or 108 which is the easier version, but one thing I did notice is that n seems to be a factor of x * y (based on the information provided in problem 108, I haven't checked any further than this). I don't know if you could use this to simplify things.

Kind regards,

Francis.
Thanks Francis, yes there's something like 2*3*5*7*11*... which makes 108 not that complicate (but tricky enough;), but 110 is even worse! And it's the only "X" in my completion list (http://projecteuler.net/index.php?secti ... file=11160) for now

You're still doing a lot better than me at the moment! http://projecteuler.net/index.php?secti ... file=12632

Kind regards,

Francis.

Posted: **Tue Jun 26, 2007 10:07 pm**

@Dreamland Fantasy:

I've been experimenting with regard to gaining the most speed out of the palindrome routines (to enhance my skills with PB). I've made a few more increases over the routines you posted last. I also did a version for testing palindromes of length 4 or 5 only by unrolling the loops.

This is what I came up with for the general case (palindromes of any length>1) and the specific case in Problem 4:

Code: Select all

; Project Euler - Problem 4
;
; A palindromic Number reads the same both ways. the largest palindrome made
; from the product of two 2-digit numbers is 9009 = 91 × 99.
;
; Find the largest palindrome made from the product of two 3-digit numbers.

#LoopTimes = 100

;- Using Demivec's palindrome routine
Procedure.l DemivecsPalindrome(A$)
  Protected I,length=Len(A$)
    len2=length>>1
    len3=length-1
    For I=len2-1 To 0 Step -1
      If (PeekB(@A$+I)<>PeekB(@A$+len3-I))
        ProcedureReturn #False
      EndIf
    Next
    ProcedureReturn #True
EndProcedure

TimeStart = GetTickCount_()
For loop = 1 To #LoopTimes
  
  min = 100
  DemResult = 0
  For a = 999 To min Step -1
    For b = a To min Step -1
      Product = a * b
      If Product > DemResult
        If DemivecsPalindrome(Str(Product))
          DemResult = Product
          min = b + 1
          If min > a
            Break 2
          EndIf
          Break
        EndIf
      EndIf
    Next
  Next
  
Next
DemTimeElapsed = GetTickCount_() - TimeStart

Procedure.l DemivecsPalindrome2(A$) ;only test palindromes of length 5 or 6
  Protected length=Len(A$)
  If length=6
    If (PeekB(@A$)=PeekB(@A$+5)) And (PeekB(@A$+1)=PeekB(@A$+4)) And (PeekB(@A$+2)=PeekB(@A$+3))
      ProcedureReturn #True
    Else
      ProcedureReturn #False
    EndIf
  Else
    If (PeekB(@A$)=PeekB(@A$+4)) And (PeekB(@A$+1)=PeekB(@A$+3))
      ProcedureReturn #True
    Else
      ProcedureReturn #False
    EndIf
  EndIf
EndProcedure

TimeStart = GetTickCount_()
For loop = 1 To #LoopTimes
  
  min = 100
  DemResult2 = 0
  For a = 999 To min Step -1
    For b = a To min Step -1
      Product = a * b
      If Product > DemResult2
        If DemivecsPalindrome2(Str(Product))
          DemResult2 = Product
          min = b + 1
          If min > a
            Break 2
          EndIf
          Break
        EndIf
      EndIf
    Next
  Next
  
Next
DemTimeElapsed2 = GetTickCount_() - TimeStart

Text$ + "Average time elapsed for Demivec's routine: "+StrF(DemTimeElapsed / #LoopTimes, 3)+"ms (Result: " + Str(DemResult) + ")"+ Chr(10)
Text$ + "Average time elapsed for Demivec's routine2: "+StrF(DemTimeElapsed2 / #LoopTimes, 3)+"ms (Result: " + Str(DemResult2) + ")"

MessageRequester("Palindrome Comparison", Text$)

The routine to test the general case test faster on my machine, will you test it on yours to verify? The palindrome routines are used in several of the Problems and I think to have them operate as quickly as possible would definately be helpful (though for problem 4 it's a bit of an overkill

)

Posted: **Tue Jun 26, 2007 10:57 pm**

Hi demivec,

I'm using my laptop here rather than my main computer, but I get 1.766ms for my routine, 1.812ms for Demivec routine and 1.718ms for Demivec routine 2. Unfortunately these results may be skewed by the CPU throttling between clock speeds.

I'll re-run them on my main computer when I get a chance.

Kind regards,

Francis.

Posted: **Thu Jun 28, 2007 7:54 pm**

Dreamland Fantasy wrote: [...]at the moment! http://projecteuler.net/index.php?secti ... file=12632

Hi Francis, you're completing the problems very fast!

Hi Demivec, maybe you can try to solve problem 125 - it has to do also with palindromes and seems also not to be too complicate to solve...

Michael.

PureBasic Forums - English

Project Euler...