|
Doing arbitrary precision (bignum) arithmetic in Lua
|
Reply to this subject
Start a new subject
 
Refresh page
Pages: 1
2
| Posted by |
Nick Gammon
Australia (18,769 posts) bio
Forum Administrator |
| Date |
Reply #15 on Thu 26 Apr 2007 05:31 AM (UTC) [ quote
] Amended on Fri 27 Apr 2007 06:51 AM (UTC) by Nick Gammon
|
| Message |
And now the inverse operation, taking the natural logarithm:
bc.digits (100)
function ln (x)
local x = bc.number (x) -- argument converted to bignum
-- if x <= 0.5 or >= 2 take the square root and double the result
if bc.compare (x, 0.5) ~= 1 or bc.compare (x, 2) == 1 then
return ln (bc.sqrt (x)) * 2
end -- if x <= 0.5 or >= 2
local a = bc.number ((x - 1) / (x + 1))
local e = bc.number (0)
local t = bc.number (a)
for i = 1, 200, 2 do
local E = e
e = e + (t / i)
t = t * a * a
-- break if no change
if e == E then
break
end -- if no change
end -- for
return e * 2
end -- function ln
print (ln (100))
Output
4.6051701859880913680359829093687284152022029772575459520666558019351452193547049604719944101791965216
|
- Nick Gammon
www.gammon.com.au, www.mushclient.com | top |
|
| Posted by |
David Haley
USA (3,881 posts) bio
Moderator |
| Date |
Reply #16 on Thu 26 Apr 2007 06:45 AM (UTC) [ quote
] |
| Message |
| I agree that this is really nifty stuff, and some very clever coding, but I'm curious: what do people use bignum math for in MUSHclient? |
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone
http://david.the-haleys.org | top |
|
| Posted by |
Nick Gammon
Australia (18,769 posts) bio
Forum Administrator |
| Date |
Reply #17 on Thu 26 Apr 2007 07:37 AM (UTC) [ quote
] |
| Message |
They probably don't, I must admit, but it is fun stuff to play with.
I think someone famous said "after the third decimal place, no-one gives a damn". |
- Nick Gammon
www.gammon.com.au, www.mushclient.com | top |
|
| Posted by |
David Haley
USA (3,881 posts) bio
Moderator |
| Date |
Reply #18 on Thu 26 Apr 2007 07:54 AM (UTC) [ quote
] |
| Message |
Ah, ok, I was just checking. :)
Quote: I think someone famous said "after the third decimal place, no-one gives a damn". Hrmph, if only I could say the same. :-) In some of the code I am writing, I unfortunately care very much about some numbers after the third decimal... if I can make the inner loop a few tens of microseconds faster, that could mean speeding up the entire program considerably... |
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone
http://david.the-haleys.org | top |
|
| Posted by |
Nick Gammon
Australia (18,769 posts) bio
Forum Administrator |
| Date |
Reply #19 on Thu 26 Apr 2007 08:08 AM (UTC) [ quote
] |
| Message |
Yes, well, I bought an interesting book recently (Coincidences, Chaos and All That Math Jazz), and it suggested this experiment:
In your favourite spreadsheet, put the number 0.5 in cell A1, and then make A2 be "=A1^2-2", and then "fill down" the same calculation over a few dozen rows. My first 20 look like this:
0.5
-1.75
1.0625
-0.87109375
-1.241195679
-0.459433287
-1.788921055
1.20023854
-0.559427448
-1.687040931
0.846107103
-1.284102771
-0.351080073
-1.876742782
1.52216347
0.316981629
-1.899522647
1.608186286
0.58626313
-1.656295543
Now do the same in column B, but start with a very slightly different number: 0.50001.
This time the results are this:
0.50001
-1.74999
1.062465
-0.871168124
-1.241066099
-0.459754937
-1.788625398
1.199180813
-0.561965379
-1.684194913
0.836512505
-1.300246828
-0.309358186
-1.904297513
1.626349018
0.645011127
-1.583960646
0.508931328
-1.740988903
1.031042361
Notice that by the 19th row, the sign isn't even the same! (compare 0.58626313 to -1.740988903).
This is an interesting example of how retaining the decimal places is absolutely crucial to getting a meaningful answer. |
- Nick Gammon
www.gammon.com.au, www.mushclient.com | top |
|
| Posted by |
Nick Gammon
Australia (18,769 posts) bio
Forum Administrator |
| Date |
Reply #20 on Mon 16 Aug 2010 01:41 AM (UTC) [ quote
] Amended on Mon 16 Aug 2010 01:52 AM (UTC) by Nick Gammon
|
| Message |
Another interesting algorithm - GCD (Greatest common divisor)
-- See: http://en.wikipedia.org/wiki/Greatest_common_divisor
-- and http://en.wikipedia.org/wiki/Euclidean_algorithm
function gcd (a, b)
local old_digits = bc.digits (0) -- we are using integers
local temp
a = bc.number (a)
b = bc.number (b)
while not bc.iszero (b) do
temp = b
b = bc.mod (a, b)
a = temp
end -- while
bc.digits (old_digits) -- put old decimal places back
return a
end -- gcd
print (gcd (8, 12)) --> 4
print (gcd (42, 56)) --> 14
print (gcd (206, 40)) --> 2
print (gcd (12070, 41820)) --> 170
print (gcd (10362, 12397)) --> 11
In mathematics, the greatest common divisor (GCD) of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4.
|
- Nick Gammon
www.gammon.com.au, www.mushclient.com | top |
|
| Posted by |
Nick Gammon
Australia (18,769 posts) bio
Forum Administrator |
| Date |
Reply #21 on Mon 16 Aug 2010 01:47 AM (UTC) [ quote
] Amended on Mon 16 Aug 2010 01:53 AM (UTC) by Nick Gammon
|
| Message |
Given the above, we can also work out the LCM (least common multiple):
-- See: http://en.wikipedia.org/wiki/Least_common_multiple
function lcm (a, b)
a = bc.number (a)
b = bc.number (b)
return (a * b) / gcd (a, b)
end -- lcm
print (lcm (21, 6)) --> 42
print (lcm (4, 6)) --> 12
In arithmetic and number theory, the least common multiple or (LCM) of two rational numbers a and b is the smallest positive rational number that is an integer multiple of both a and b.
|
- Nick Gammon
www.gammon.com.au, www.mushclient.com | top |
|
The dates and times for posts above are shown in Universal Co-ordinated Time (UTC).
To show them in your local time you can join the forum, and then set the 'time correction' field in your profile to the number of hours difference between your location and UTC time.
8,769 views.
This is page 2, subject is 2 pages long:
1
2
Reply to this subject
Start a new subject
 
Refresh page
top
Comments to:
Gammon Software support
Forum RSS feed ( http://www.gammon.com.au/rss/forum.xml )