Square root digital expansion
Problem 080: Square root digital expansion
It is well known that if the square root of a natural number is not an integer, then it is irrational. The decimal expansion of such square roots is infinite without any repeating pattern at all.
The square root of two is 1.41421356237309504880...,
and the digital sum of the first one hundred decimal digits is 475.
For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.
Solution:
############################################################
@ ############################################################
.
g ############################################################
0
^9$># #< v v < v <
$ v_^#-"d"\+1:< <>$"<">1-::9+5g\9+1p:#^_$0>:::9+3g55+%55+*v
>090p2>:20p"d">::*20g-#v_$^|!:-1p5+8\-g07g06p04 # <\
# v"<":$_^# !:-1< >::9+1g40g-60p:9+3g20g45***70p0>70g60g`!|5
^ <>1-:0\9+1p:0\v ^ ";"p04* :g02p5"D"0p<#+ 65
|:p5+9\0:p3+9< >9+1g-!#v_::9+5g\9+1g`!#v_$20g1-20^ 1 0+
>$"D"1p"d"020p>20g:*40p "<">1-::9+3g20g 45***40gv ^p06+"d"g<+
^ _> #v^#-"<":+1< |:p5+9\%"d"p 04/"d":+<v3+9\+/+55g3<
v_v^\g5+9::<0 $< v:+1p<#
^p02+1g02$>#<# ^# < > ";"-|
^ !:-1p020p09+g09g02p3"D"+g02*+55%+55g3"D"$<
Explanation:
A short look to Wikipedia finds us a neat algorithm to calculate the square-root digit-by-digit.
I have optimized it a little bit with the target to use not so many variables:
IEnumerable<int> DRoot(int r)
{
BigInteger c = r;
BigInteger p = 0;
int x = 0;
for (ii = 0; ii < 100; ii++)
{
for (x = 0;(x+1)*(20*p + (x+1)) <= c;x++);
c = 100*c - 2000*p*x - 100*x*x;
p = p*10 + x;
}
return p;
}The algorithm is pretty simple, but god do I hate long addition/multiplication in Befunge.
We need 120 base-10 digits for the numbers pand c.
In our program we use base-100 notation. This way we can fit the numbers in a single befunge-93 row
and can simply multiply by 100 with a single left shift operation.
| Interpreter steps: | 540 417 723 |
| Execution time (BefunExec): | 1min 56s (4.64 MHz) |
| Program size: | 69 x 18 (fully conform befunge-93) |
| Solution: | 40886 |
| Solved at: | 2015-09-11 |