QB64.org Forum

Active Forums => Programs => Topic started by: bplus on May 04, 2021, 04:45:08 pm

Title: Euler's Sum of Powers Conjecture (Disproof) - Rosetta Code
Post by: bplus on May 04, 2021, 04:45:08 pm

I am sure this could be speeded up but not a long wait here:

Code: QB64: [Select]

1. _Title "Euler's Sum of Powers Conjecture (Disproof)" ' b+ 2021-05-04
2. Dim As _Unsigned _Integer64 a, b, c, d, e, max, sumb, sumc, sumd
3. Dim p5(1 To 250) As _Unsigned _Integer64
4. For c = 1 To 250
5.     p5(c) = c * c * c * c * c
6. Next
7. max = p5(250)
8. For a = 1 To 250
9.     Print a 'show progress on slowest integer
10.     For b = a + 1 To 250
11.         If p5(a) + p5(b) > max Then Exit For Else sumb = p5(a) + p5(b)
12.         For c = b + 1 To 250
13.             If sumb + p5(c) > max Then Exit For Else sumc = sumb + p5(c)
14.             For d = c + 1 To 250
15.                 If sumc + p5(d) > max Then Exit For Else sumd = sumc + p5(d)
16.                 For e = 1 To 250
17.                     If sumd = p5(e) Then Print a; "^ 5 +"; b; "^ 5 +"; c; "^ 5 +"; d; "^ 5 ="; e; "^ 5": End
18.                 Next
19.             Next
20.         Next
21.     Next
22. Next
23.  

About 2 mins.

Title: Re: Euler's Sum of Powers Conjecture (Disproof) - Rosetta Code
Post by: jack on May 05, 2021, 04:02:32 am

hi bplus :)
if you feel adventurous, you could edit qb64_1.5_win_x64\internal\c\makeline_win.txt and add -O2 after g++ for about 170% speedup
that is if you are running the 64-bit version
to make timing easier, I made a small addition

Code: QB64: [Select]

1. _Title "Euler's Sum of Powers Conjecture (Disproof)" ' b+ 2021-05-04
2. Dim As _Unsigned _Integer64 a, b, c, d, e, max, sumb, sumc, sumd
3. Dim p5(1 To 250) As _Unsigned _Integer64
4. Dim t As Double
5. t = Timer
6. For c = 1 To 250
7.     p5(c) = c * c * c * c * c
8. Next
9. max = p5(250)
10. For a = 1 To 250
11.     Print a 'show progress on slowest integer
12.     For b = a + 1 To 250
13.         If p5(a) + p5(b) > max Then Exit For Else sumb = p5(a) + p5(b)
14.         For c = b + 1 To 250
15.             If sumb + p5(c) > max Then Exit For Else sumc = sumb + p5(c)
16.             For d = c + 1 To 250
17.                 If sumc + p5(d) > max Then Exit For Else sumd = sumc + p5(d)
18.                 For e = 1 To 250
19.                     If sumd = p5(e) Then
20.                         Print a; "^ 5 +"; b; "^ 5 +"; c; "^ 5 +"; d; "^ 5 ="; e; "^ 5"
21.                         Print Timer - t
22.                         End
23.                     End If
24.                 Next
25.             Next
26.         Next
27.     Next
28. Next
29.  

[edit] you could also add instead of just -O2 add -O2 -march=native
-march=native might speed it up a bit more than -O2 alone

Title: Re: Euler's Sum of Powers Conjecture (Disproof) - Rosetta Code
Post by: bplus on May 05, 2021, 11:50:52 am

Thanks jack, I was hoping someone could speedup with smarter application of math.

FreeBasic version uses limits and Mod but don't know why.
I tried the limits and didn't make significant difference seems like the EXIT FOR condition covers the limits already?
http://rosettacode.org/wiki/Euler%27s_sum_of_powers_conjecture#FreeBASIC

Title: Re: Euler's Sum of Powers Conjecture (Disproof) - Rosetta Code
Post by: _vince on May 05, 2021, 01:15:11 pm

Wow, I just noticed this in the FreeBASIC version:

Code: [Select]

Exit For, For

and it does what you'd expect, pretty slick.  More info: https://www.freebasic.net/wiki/KeyPgExit (https://www.freebasic.net/wiki/KeyPgExit)
Another idea for QB64 in its path to VB.NET glory.


Another interesting thought regarding this, Bill and Steve should chime in.  We know that the N-th order generalization for repeating a line of code without retyping it is a FOR ... TO N loop.  But what is the N-th order generalization for N nested FOR loops, without typing it out?  It can be done with recursion, something like:

Code: [Select]

SUB f(a,b,c,...)
    FOR i=a TO b
        'do stuff
        CALL f( h(a), g(a), ... )
    NEXT
END SUB


Title: Re: Euler's Sum of Powers Conjecture (Disproof) - Rosetta Code
Post by: jack on May 05, 2021, 02:17:50 pm

bplus, I adapted the freeBasic version that you linked to QB64, it's quite fast

Code: QB64: [Select]

1. ' http://rosettacode.org/wiki/Euler%27s_sum_of_powers_conjecture#FreeBASIC
2. ' version 14-09-2015
3.  
4. ' some constants calculated when the program is compiled
5.  
6. Dim As Double t: t = Timer
7. Const max = 250
8. Const pow5_max = max * max * max * max * max
9. ' limit x1, x2, x3
10. Const limit_x1 = (pow5_max / 4) ^ 0.2
11. Const limit_x2 = (pow5_max / 3) ^ 0.2
12. Const limit_x3 = (pow5_max / 2) ^ 0.2
13.  
14. ' ------=< MAIN >=------
15.  
16. Dim As _Unsigned _Integer64 pow5(max), ans1, ans2, ans3
17. Dim As _Unsigned _Integer64 x1, x2, x3, x4, x5, m1, m2
18.  
19. Cls: Print
20.  
21. For x1 = 1 To max
22.     pow5(x1) = x1 * x1 * x1 * x1 * x1
23. Next x1
24.  
25. For x1 = 1 To limit_x1
26.     For x2 = x1 + 1 To limit_x2
27.         m1 = x1 + x2
28.         ans1 = pow5(x1) + pow5(x2)
29.         If ans1 > pow5_max Then Exit For
30.         For x3 = x2 + 1 To limit_x3
31.             ans2 = ans1 + pow5(x3)
32.             If ans2 > pow5_max Then Exit For
33.             m2 = (m1 + x3) Mod 30
34.             If m2 = 0 Then m2 = 30
35.             For x4 = x3 + 1 To max - 1
36.                 ans3 = ans2 + pow5(x4)
37.                 If ans3 > pow5_max Then Exit For
38.                 For x5 = x4 + m2 To max Step 30
39.                     If ans3 < pow5(x5) Then Exit For
40.                     If ans3 = pow5(x5) Then
41.                         Print x1; "^5 + "; x2; "^5 + "; x3; "^5 + "; _
42.                               x4; "^5 = "; x5; "^5"
43.                         GoTo skip
44.                     End If
45.                 Next x5
46.             Next x4
47.             skip:
48.         Next x3
49.     Next x2
50. Next x1
51.  
52. Print
53. Print Timer - t
54. Print "done"
55.  

Title: Re: Euler's Sum of Powers Conjecture (Disproof) - Rosetta Code
Post by: bplus on May 05, 2021, 02:25:21 pm

OH wow jack! nice improvement, I think I was trying everything with print each line and that dragged on for hours... so it does make a significant difference.

_vince, I missed the Exit For, For that's interesting, as your suggestion for QB64.

Text Only | Text with Attachments