Yeah yeah, there's something 'bout you baby I likeIt's a bit worrisome when I quote musicians from last century, but I do like mLite. Granted, I don't dream about it, but it's fun to figure out how to do things in a functional way.
-- Status Quo, 1981.
In this case I was wanting to solve the RosettaCode challenge Arbitrary-precision integers (included) which has one calculate 5^4^3^2, find out how many digits there are and then display the top 20 digits and bottom 20 digits. Bignums weren't a challenge, as they are supported natively in mLite. No, the biggest challenge was figuring out how many digits. 5^4^3^2 is an extremely large number, with 183231 digits and all of my first attempts did not complete even after running for a day.
mLite's creator, Nils M. Holm, suggested I use logarithms. However, logarithms aren't built in to mLite yet, so I had to cook up my own logarithm library. So how do you calculate logarithms by hand? I dug around a bit and found an article on Quora entitled How can we calculate the logarithms by hand without using any calculator?. Harald Overbeek's description formed the basis for the mLite code below.
fun ntol (0, x) = if len x < 1 then  else x | (n, x) = ntol (n div 10, (n mod 10) :: x) | n = ntol (n, ) ;
ntolconverts a number to a list.
fun powers_of_10 9 = 1000000000 | 8 = 100000000 | 7 = 10000000 | 6 = 1000000 | 5 = 100000 | 4 = 10000 | 3 = 1000 | 2 = 100 | 1 = 10 | 0 = 1 ;
powers_of_10is a precomputation of all the powers I knew I'd encounter during the calculation. This alone sped up the code a lot.
fun size (c, 0) = c | (c, n > 9999999999) = size (c + 10, trunc (n / 10000000000)) | (c, n) = size (c + 1, trunc (n / 10)) | n = size ( 0, trunc (n / 10)) ;
sizeworks out the number of digits by keeping track of how many calculations it takes to divide the number by 10 until the remainder is zero.
fun makeVisible L = map (fn x = if int x then chr (x + 48) else x) L
makeVisibleturns an array of digits into a string, with handling for non-numeric elements
fun log10 (n, 0, x) = stonThen
implodemakeVisible ` rev x | (n, decimals, x) = let val n' = n^10; val size_n' = size n' in log10 (n' / powers_of_10 size_n', decimals - 1, size_n' :: x) end | (n, decimals) = let val size_n = size n in log10 (n / 10^size_n, decimals, #"." :: rev (ntol size_n) @ ) end ;
log10ties it all together. The second parameter specifies the number of digits precision. Below I've specified 6.
Being somewhat mathematically challenged, I still had to figure out how to use the library I had made to calculate the digits. Thankfully, there's a mathematics community on StackExchange. They helped me out a lot. Now I could work out the number of digits in the number by rounding up the result of log10(5) * 4^9 (seeing as 3^2 is 9).
Thus I ended up with
val fourThreeTwo = 4^3^2; val fiveFourThreeTwo = 5^fourThreeTwo; val digitCount = trunc (log10(5,6) * fourThreeTwo + 0.5); print "Count = "; println digitCount; val end20 = fiveFourThreeTwo mod (10^20); print "End 20 = "; println end20; val top20 = fiveFourThreeTwo div (10^(digitCount - 20)); print "Top 20 = "; println top20;Which, after 1 hour and 9 minutes on an AMD A6 cpu, gave
© Copyright Bruce M. Axtens, 2015