Page 1 of 1
Handling really big numbers
Posted: Tue May 01, 2012 11:21 am
by 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
Re: Handling really big numbers
Posted: Wed May 02, 2012 1:00 am
by 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
Re: Handling really big numbers
Posted: Wed May 02, 2012 10:13 pm
by Maxiogee
Mark wrote: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.
Re: Handling really big numbers
Posted: Wed May 02, 2012 10:25 pm
by 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
Re: Handling really big numbers
Posted: Wed May 02, 2012 10:42 pm
by 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
Re: Handling really big numbers
Posted: Wed May 02, 2012 11:32 pm
by 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.
Re: Handling really big numbers
Posted: Thu May 03, 2012 8:26 pm
by 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