Largest exponential

2017-01-13

Problem 099: Largest exponential

Description:

Comparing two numbers written in index form like 2^11 and 3^7 is not difficult, as any calculator would confirm that 2^11 = 2048 < 3^7 = 2187.

However, confirming that 632382^518061 > 519432^525806 would be much more difficult, as both numbers contain over three million digits.

Using base_exp.txt, a 22K text file containing one thousand lines with a base/exponent pair on each line, determine which line number has the greatest numerical value.

NOTE: The first two lines in the file represent the numbers in the example given above.

Solution:

v$$$$$$                                           519432,525806
XX  00v         $<                               632382,518061
    v  <p15g11p16_^#`g16:p<                       78864,613712
>0:5 1p vv               <1                       466580,530130
v $ $  #<v+1g12+*+55\p   12\-*86<                780495,510032
>#  > 0"2">:11gg:48*-0`!#^_:","- |                525895,525320
^p110p16< ^               # +1\0$<                15991,714883
   vp04+g04     <   vp06< +                       960290,502358
: #>1-#v\#/ #2<^      <: 1                       760018,511029
!v<| :\<***"@}}"g01<>$ ^ g                       166800,575487
v_   20p10p01>:2*10g`| |>1^                       210884,564478
$   >$30p0:4v^\+1\*2 <v<1                         555151,523163
5 5>v  p05p0<     >>$40#+v                        681146,515199
1 0#>030g"}}@"**`!|^ $< *g                        563395,522587
g g|!`g03***"@}}"2<p < :g2                        738250,512126
. +>1+30g:*"}}@"**/30^ $00                        923525,503780
@ >50p30g2/30p20g50g>:!|6g                        595148,520429
          > #2/#\\#-^#1<^<                        177108,572629
                                                  750923,511482
                                                  440902,532446
                                                  881418,505504
                                                  ...
                                                  ...

Download

This program is too big to display/execute here, click [download] to get the full program.

Explanation:

For every number we normalize the Exponentiation to base 2. (We search the equivalent Power 2^x). And then we only compare the exponents with each other, practically this means we compare the length of the number in binary representation.

We chose 2 as our base because this way we don't have to worry too much about the precision of our calculations (befunge has no native floating point values). If we would have found two entries with the same (overall highest) exponent, we would have to calculate the exponent to a higher precision, but fortunately this did not happen.

From b^e we can get the normalized fraction 2^(e * log2(b)). But because befunge has no log2 operator we have to go through the dirty work of manually approximating log2.

We use this algorithm to calculate log2.

First we calculate the integer part by simple searching the biggest number 2^n where 2^n < b

Then the real part equals log2(2^(-n) * b), because we don't want to caclulate with real numbers we insert a Precision factor F (in this program we used a value of 1 million).

Now y = 2^-n * b and rp = log2(y). We calculate y by dividing b n-times with two.

Our final result will be r = n * e + rp * e. We can already calculate n*e, the only missing part is rp*e, which we will call exporp.

Then we repeat the following steps until the value of exporp is no longer changing:

count the number of times m we have to square y until y >= 2
y = y^(2^m) / 2
add m to msum, the collective sum of all calculated m values until now
divide e msum-times by two and add the result to exporp

Now we have calculated exporp, our result is r = n * e + exporp.

With this method we can calculate the exponent of our normalized exponentiation. Next we simply iterate through the whole inpt and search the line number with the greatest base2-exponent.