Project Euler with Befunge
Problem 099: Largest exponential
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.
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
For every number we normalize the Exponentiation to base 2.
(We search the equivalent Power
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.
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 < 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).
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
which we will call
Then we repeat the following steps until the value of exporp is no longer changing:
- count the number of times
mwe have to square
y >= 2
y = y^(2^m) / 2
msum, the collective sum of all calculated
mvalues until now
msum-times by two and add the result to
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.
|Interpreter steps:||5 072 021|
|Execution time (BefunExec):||1.11s (4.58 MHz)|
|Program size:||63 x 1000|