-
Notifications
You must be signed in to change notification settings - Fork 1
/
Euler_Problem-044.b93
48 lines (35 loc) · 2.03 KB
/
Euler_Problem-044.b93
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
>v%%% %%%% > v
v06p09:/2*-1*3:p06::+1<vg07g09 << <
g$ >:70p:3*1 v # >0v>vv p03+g03*2:p04-\g04+g03:<
v <3 pp2# v/4 < >:30g+40g`! |
1# > 4**1+:0^ 40>0g>:40g`#^_>:|:/4p03/2g03< $
>-:|^6-p08:/2*-< # >^ >30g2/30p4/^ >$30g:*-30g\ |
8 >$$ ^v030:+1**46+g09g08 ># !# # _^
>::**::**8*20p1 ^v>vv p03+g03*2:p04-\g04+g03:<@.-g08g0 9<
pp2# v/4 < >:30g+40g`! | ^5%6 <$
40>0g>:40g`#^_>:|:/4p03/2g03< >$ ^
>^ >30g2/30p4/^ >$30g:*-30g\ #^_6%5-#^_^
[20] 2^30 const (muss vorher gesetzt sein)
[30] res
[40] op
[60] i
[70] j
[80] m
[90] n
integer-square: (see http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Binary_numeral_system_.28base_2.29)
>0v>vv p03+g03*2:p01-\g01+g03:<
3 pp2# v/4 < >:30g+10g`! |
0^ 10>0g>:10g`#^_>:|:/4p03/2g03<
>^ >30g2/30p4/^ >$30g
isPentagonal:
>0v>vv p03+g03*2:p01-\g01+g03:<
3 pp2# v/4 < >:30g+10g`! |
64**1+:0^ 10>0g>:10g`#^_>:|:/4p03/2g03< >$ > // NO PENT
>^ >30g2/30p4/^ >$30g:*-30g\ #^_6%5-#^_ // PENT
-------------------------------------------------------------------------------
My first attempt at this problem took over 5 hours to compute and had a complexity of O(n^3).
The problem is that you need a square root to inverse the pentagonal formula and Befunge has no square root function.
So I needed to implement my own version of integer square roots in Befunge (see [wikipedia](http://en.wikipedia.org/wiki/Methods_of_computing_square_roots)).
The program is still not really fast but it's good that I managed to speed it up to a time where you can execute it without waiting the whole night.
Also this program is nicely compact, by the time I'm writing this my Befunge interpreter [BefunExec](http://www.mikescher.de/programs/view/BefunGen) has gotten a display of all possible paths a program can take.
And if you look at the graph of this program, it looks pretty interesting...