[mLite] Arbitrary Precision Integers and Logarithms

Yeah yeah, there's something 'bout you baby I like

-- Status Quo, 1981.

It'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.

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 [0] else x
       | (n, x) = ntol (n div 10, (n mod 10) :: x)
       | n      = ntol (n, [])
;

ntol converts 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_10 is 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))
;

size works 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

makeVisible turns an array of digits into a string, with handling for non-numeric elements

fun log10 (n, 0, x) = ston  implode  makeVisible ` 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
;

Then log10 ties 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

>mlite -f 5p4p3p2.m
 Count = 183231
 End 20 = 92256259918212890625
 Top 20 = 62060698786608744707 

A nice change from my day job which centres around JavaScript, Peloton, HTML, PHP and the odd bit of T-SQL. Enjoy!

© Copyright Bruce M. Axtens, 2015