Handling really big numbers

[Maxiogee]

There was an external for HyperCard which allowed the user to deal with numbers which exceeded that application's limits.

I wonder is there a workaround, or an external, which will allow me to work with a really big number.

Project Euler (a wonderful little source for programming exercises) asks in problem 25 "What is the first term in the Fibonacci sequence to contain 1000 digits?"

I can get as far as term 1470 which is

72836013092016285809643117......307018801152

and which contains 307 digits before I get the dreaded "inf".

I'd really like to be able to use LiveCode to solve this.

My script is

Code: Select all

On MouseUp
   put "n" into Thou
   put 1 into start
   put 1 into Feed
   put 0 into Nex
   put 2 into term
   repeat until thou = "y"
      Put start + feed into Nex
      put feed into start
      put nex into feed
      add 1 to term
      if term mod 10 = 0 then
         wait 1 millisecond
         put term && number of chars in feed && feed
      end if
      if number of chars in feed > 999 then
         put term && feed into field "Display"
      end if
   end repeat
end mouseUp

[Mark]

Hi,

I believe the purpose of the exercise is that you find a way to get around the limit in a clever way instead of finding some programming tool that just does the job for you.

Kind regards,

Mark

[Maxiogee]

Hi,

I believe the purpose of the exercise is that you find a way to get around the limit in a clever way instead of finding some programming tool that just does the job for you.

Kind regards,

Mark

Spoken like someone who has solved it. Care to pass on any tips?

And anyway, looking for an external is, for me, a clever way around the problem.

[Mark]

Hi,

How would you solve it if you were using pen and paper and had an unlimited amount of time? Simulate that with a computer programme. This is the answer to quite a few exercises on the Euler website.

I had a script with a solution in a button somewhere in the margin of a stack and just a few days ago I deleted that button (really true). I'm so sorry.

One hint: instead of adding 1 to the entire number, add 1 to the last digit and add 1 to the previous digit if the last digit is larger than 9 and then reset the last digit to 0 and continue with the before-previous digit if necessary et cetera. Repeat recursively until you have updated all digits.

It is sufficient to check if a number is a divisor only once. Remember the divisors in a return-delimited list and you can just check if a number is among the lines of that list.

Kind regards,

Mark

[bn]

Hi Max,

this is way above my math level but I remember a discussion on the use-list
http://runtime-revolution.278305.n4.nab ... ml#a337595
that Mark Wieder started. He is also on this forum here and maybe he will chime in.
Kind regards
Bernd

[mwieder]

I did start that discussion a few years ago for exactly the same reason: how do you deal with numbers that overflow the bounds of what internal math packages can handle? And the answer, as Mark S has suggested, is to do it yourself, managing the additions and the overflows. And the reason it's on the Project Euler list is to get you to think through these things and come up with a clever solution that does the trick. It's much easier to do this in LiveCode because the xtalk language does all the gnarly string-to-longInt and longInt-to-string transformations for you.

[Maxiogee]

Thanks for the responses folks.

In bed last night - where all my best thinking happens - I came up with this....

Code: Select all

on mouseup
   set lockscreen to true
   put 1 into item 1000 of seed
   put 1 into item 1000 of newNum
   put 0 into carry
   put 2 into fibterm
   repeat until item 1 of newNum = 1
      repeat with b = 1 to 1000
         put (item 1001-b of seed)+(item 1001-b of newnum)+carry into Holder
         if number of chars in holder = 2 then 
            put char 1 of holder into carry
         else put 0 into carry	
         put last char of holder into item 1001-b of FibNo
      end repeat
      add 1 to fibterm	
      put newnum into seed
      put FibNo into newnum
      put empty into fibno
      put 0 into carry
      if item 1 of newNum = 1 then
         put fibterm  && " = " &&  newnum into field "Display"
      end if
   end repeat
set lockscreen to false
end mouse up