Pythagorean triples: Difference between revisions
added FreeBASIC
m (→{{eader|Ruby}}: restorered header) |
(added FreeBASIC) |
||
Line 1,352:
Up to 10000000 9706567 triples 702309 primitives
Up to 100000000 113236940 triples 7023027 primitives</pre>
=={{header|FreeBASIC}}==
The upper limit is set to 12(10^12), this will take 3-4 hours.
If you can't wait that long better lower it to 11(10^11).
===Version 1===
Normal version
<lang freebasic>' version 30-05-2016
' compile with: fbc -s console
' primitive pythagoras triples
' a = m^2 - n^2, b = 2mn, c = m^2 + n^2
' m, n are positive integers and m > n
' m - n = odd and GCD(m, n) = 1
' p = a + b + c
' max m for give perimeter
' p = m^2 - n^2 + 2mn + m^2 + n^2
' p = 2mn + m^2 + m^2 + n^2 - n^2 = 2mn + 2m^2
' m >> n and n = 1 ==> p = 2m + 2m^2 = 2m(1 + m)
' m >> 1 ==> p = 2m(m) = 2m^2
' max m for given perimeter = sqr(p / 2)
Function gcd(x As UInteger, y As UInteger) As UInteger
Dim As UInteger t
While y
t = y
y = x Mod y
x = t
Wend
Return x
End Function
Sub pyth_trip(limit As ULongInt, ByRef trip As ULongInt, ByRef prim As ULongInt)
Dim As ULongInt perimeter, lby2 = limit Shr 1
Dim As UInteger m, n
Dim As ULongInt a, b, c
For m = 2 To Sqr(limit / 2)
For n = 1 + (m And 1) To (m - 1) Step 2
' common divisor, try next n
If (gcd(m, n) > 1) Then Continue For
a = CULngInt(m) * m - n * n
b = CULngInt(m) * n * 2
c = CULngInt(m) * m + n * n
perimeter = a + b + c
' perimeter > limit, since n goes up try next m
If perimeter >= limit Then Continue For, For
prim += 1
If perimeter < lby2 Then
trip += limit \ perimeter
Else
trip += 1
End If
Next n
Next m
End Sub
' ------=< MAIN >=------
Dim As String str1, buffer = Space(14)
Dim As ULongInt limit, trip, prim
Dim As Double t, t1 = Timer
Print "below triples primitive time"
Print
For x As UInteger = 1 To 12
t = Timer
limit = 10 ^ x : trip = 0 : prim = 0
pyth_trip(limit, trip, prim)
LSet buffer, Str(prim) : str1 = buffer
Print Using "10^## ################ "; x; trip;
If x > 7 Then
Print str1;
Print Using " ######.## sec."; Timer - t
Else
Print str1
End If
Next x
Print : Print
Print Using "Total time needed #######.## sec."; Timer - t1
' empty keyboard buffer
While InKey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End</lang>
<pre>below triples primitive time
10^ 1 0 0
10^ 2 17 7
10^ 3 325 70
10^ 4 4858 703
10^ 5 64741 7026
10^ 6 808950 70229
10^ 7 9706567 702309
10^ 8 113236940 7023027 0.94 sec.
10^ 9 1294080089 70230484 10.13 sec.
10^10 14557915466 702304875 109.75 sec.
10^11 161750315680 7023049293 1204.56 sec.
10^12 1779214833461 70230492763 13031.84 sec.
Total time needed 14357.31 sec.</pre>
===Version 2===
Attempt to make a faster version (about 20% faster)
<lang freebasic>' version 30-05-2016
' compile with: fbc -s console
' max m for give perimeter
' p = m^2 - n^2 + 2mn + m^2 + n^2
' p = 2mn + m^2 + m^2 + n^2 - n^2 = 2mn + 2m^2
' m >> n and n = 1 ==> p = 2m + 2m^2 = 2m(1 + m)
' m >> 1 ==> p = 2m(m) = 2m^2
' max m for given perimeter = sqr(p / 2)
Function gcd(x As UInteger, y As UInteger) As UInteger
Dim As UInteger t
While y
t = y
y = x Mod y
x = t
Wend
Return x
End Function
Sub pyth_trip_fast(limit As ULongInt, ByRef trip As ULongInt, ByRef prim As ULongInt)
Dim As ULongInt perimeter, lby2 = limit Shr 1
Dim As UInteger mx2 = 4
For m As UInteger = 2 To Sqr(limit / 2)
perimeter = (CULngInt(m) * m * 2) - IIf(m And 1, 0, m * 2)
mx2 = mx2 + 4
For n As UInteger = 1 + (m And 1) To (m - 1) Step 2
perimeter += mx2
' common divisor, try next n
If (gcd(m, n) > 1) Then Continue For
' perimeter > limit, since n goes up try next m
If perimeter >= limit Then Continue For, For
prim += 1
If perimeter < lby2 Then
trip += limit \ perimeter
Else
trip += 1
End If
Next n
Next m
End Sub
' ------=< MAIN >=------
Dim As String str1, buffer = Space(14)
Dim As ULongInt limit, trip, prim
Dim As Double t, t1 = Timer
Print "below triples primitive time"
Print
For x As UInteger = 1 To 12
t = Timer
limit = 10 ^ x : trip = 0 : prim = 0
pyth_trip_fast(limit, trip, prim)
LSet buffer, Str(prim) : str1 = buffer
Print Using "10^## ################ "; x; trip;
If x > 7 Then
Print str1;
Print Using " ######.## sec."; Timer - t
Else
Print str1
End If
Next x
Print : Print
Print Using "Total time needed #######.## sec."; Timer - t1
' empty keyboard buffer
While InKey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End</lang>
<pre>below triples primitive time
10^ 1 0 0
10^ 2 17 7
10^ 3 325 70
10^ 4 4858 703
10^ 5 64741 7026
10^ 6 808950 70229
10^ 7 9706567 702309
10^ 8 113236940 7023027 0.66 sec.
10^ 9 1294080089 70230484 7.48 sec.
10^10 14557915466 702304875 83.92 sec.
10^11 161750315680 7023049293 945.95 sec.
10^12 1779214833461 70230492763 10467.94 sec.
Total time needed 11506.01 sec.</pre>
The time needed is about 11 times the time needed for the previous limit.
To calculate 10^12 with the fast version that would take about 32 hours.
The variable that holds the number of triples will eventual overflow
at 10^18 - 10^19. To reach that stage you need the program to run
for a few years.
=={{header|Go}}==
| |||