90 lines
2.1 KiB
Text
90 lines
2.1 KiB
Text
' 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
|