How to resolve the algorithm Pythagorean triples step by step in the Forth programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Pythagorean triples step by step in the Forth programming language
Table of Contents
Problem Statement
A Pythagorean triple is defined as three positive integers
( a , b , c )
{\displaystyle (a,b,c)}
where
a < b < c
{\displaystyle a<b<c}
, and
a
2
b
2
=
c
2
.
{\displaystyle a^{2}+b^{2}=c^{2}.}
They are called primitive triples if
a , b , c
{\displaystyle a,b,c}
are co-prime, that is, if their pairwise greatest common divisors
g c d
( a , b )
g c d
( a , c )
g c d
( b , c )
1
{\displaystyle {\rm {gcd}}(a,b)={\rm {gcd}}(a,c)={\rm {gcd}}(b,c)=1}
. Because of their relationship through the Pythagorean theorem, a, b, and c are co-prime if a and b are co-prime (
g c d
( a , b )
1
{\displaystyle {\rm {gcd}}(a,b)=1}
). Each triple forms the length of the sides of a right triangle, whose perimeter is
P
a + b + c
{\displaystyle P=a+b+c}
.
The task is to determine how many Pythagorean triples there are with a perimeter no larger than 100 and the number of these that are primitive.
Deal with large values. Can your program handle a maximum perimeter of 1,000,000? What about 10,000,000? 100,000,000? Note: the extra credit is not for you to demonstrate how fast your language is compared to others; you need a proper algorithm to solve them in a timely manner.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Pythagorean triples step by step in the Forth programming language
Source code in the forth programming language
\ Two methods to create Pythagorean Triples
\ this code has been tested using Win32Forth and gforth
: pythag_fibo ( f1 f0 -- )
\ Create Pythagorean Triples from 4 element Fibonacci series
\ this is called with the first two members of a 4 element Fibonacci series
\ Price and Burkhart have two good articles about this method
\ "Pythagorean Tree: A New Species" and
\ "Heron's Formula, Descartes Circles, and Pythagorean Triangles"
\ Horadam found out how to compute Pythagorean Triples from Fibonacci series
\ compute the two other members of the Fibonacci series and put them in
\ local variables. I was unable to do this with out using locals
2DUP + 2DUP + 2OVER 2DUP + 2DUP +
LOCALS| f3 f2 f1 f0 |
wk_level @ 9 .r f0 8 .r f1 8 .r f2 8 .r f3 8 .r
\ this block calculates the sides of the Pythagorean Triangle using single precision
\ f0 f3 * 14 .r \ side a (always odd)
\ 2 f1 * f2 * 10 .r \ side b (a multiple of 4)
\ f0 f2 * f1 f3 * + 10 .r \ side c, the hyponenuse, (always odd)
\ this block calculates double precision values
f0 f3 um* 15 d.r \ side a (always odd)
2 f1 * f2 um* 15 d.r \ side b (a multiple of 4)
f0 f2 um* f1 f3 um* d+ 17 d.r cr \ side c, the hypotenuse, (always odd)
MAX_LEVEL @ wk_LEVEL @ U> IF \ TRUE if MAX_LEVEL > WK_LEVEL
wk_level @ 1+ wk_level !
\ this creates a teranary tree of Pythagorean triples
\ use a two of the members of the Fibonacci series as seeds for the
\ next level
\ It's the same tree created by Barning or Hall using matrix multiplication
f3 f1 recurse
f3 f2 recurse
f0 f2 recurse
wk_level @ 1- wk_level !
else
then
drop drop drop drop ;
\ implements the Fibonacci series -- Pythagorean triple
\ the stack contents sets how many iteration levels there will be
: pf_test
\ the stack contents set up the maximum level
max_level !
0 wk_level !
cr
\ call the function with the first two elements of the base Fibonacci series
1 1 pythag_fibo ;
: gcd ( a b -- gcd )
begin ?dup while tuck mod repeat ;
\ this is the classical algorithm, known to Euclid, it is explained in many
\ books on Number Theory
\ this generates all primitive Pythagorean triples
\ i -- inner loop index or current loop index
\ j -- outer loop index
\ stack contents is the upper limit for j
\ i and j can not both be odd
\ the gcd( i, j ) must be 1
\ j is greater than i
\ the stack contains the upper limit of the j variable
: pythag_ancn ( limit -- )
cr
1 + 2 do
i 1 and if 2 else 1 then
\ this sets the start value of the inner loop so that
\ if the outer loop index is odd only even inner loop indices happen
\ if the outer loop index is even only odd inner loop indices happen
i swap do
i j gcd 1 - 0> if else \ do this if gcd( i, j ) is 1
j 5 .r i 5 .r
\ j j * i i * - 12 .r \ a side of Pythagorean triangle (always odd)
\ i j * 2 * 9 .r \ b side of Pythagorean triangle (multiple of 4)
\ i i * j j * + 9 .r \ hypotenuse of Pythagorean triangle (always odd)
\ this block calculates double precision Pythagorean triple values
j j um* i i um* d- 15 d.r \ a side of Pythagorean triangle (always odd)
i j um* d2* 15 d.r \ b side of Pythagorean triangle (multiple of 4)
i i um* j j um* d+ 17 d.r \ hypotenuse of Pythagorean triangle (always odd)
cr then 2 +loop \ keep i being all odd or all even
loop ;
Current directory: C:\Forth ok
FLOAD 'C:\Forth\ancien_fibo_pythag.F' ok
ok
ok
ok
3 pf_test
0 1 1 2 3 3 4 5
1 3 1 4 5 15 8 17
2 5 1 6 7 35 12 37
3 7 1 8 9 63 16 65
3 7 6 13 19 133 156 205
3 5 6 11 17 85 132 157
2 5 4 9 13 65 72 97
3 13 4 17 21 273 136 305
3 13 9 22 31 403 396 565
3 5 9 14 23 115 252 277
2 3 4 7 11 33 56 65
3 11 4 15 19 209 120 241
3 11 7 18 25 275 252 373
3 3 7 10 17 51 140 149
1 3 2 5 7 21 20 29
2 7 2 9 11 77 36 85
3 11 2 13 15 165 52 173
3 11 9 20 29 319 360 481
3 7 9 16 25 175 288 337
2 7 5 12 17 119 120 169
3 17 5 22 27 459 220 509
3 17 12 29 41 697 696 985
3 7 12 19 31 217 456 505
2 3 5 8 13 39 80 89
3 13 5 18 23 299 180 349
3 13 8 21 29 377 336 505
3 3 8 11 19 57 176 185
1 1 2 3 5 5 12 13
2 5 2 7 9 45 28 53
3 9 2 11 13 117 44 125
3 9 7 16 23 207 224 305
3 5 7 12 19 95 168 193
2 5 3 8 11 55 48 73
3 11 3 14 17 187 84 205
3 11 8 19 27 297 304 425
3 5 8 13 21 105 208 233
2 1 3 4 7 7 24 25
3 7 3 10 13 91 60 109
3 7 4 11 15 105 88 137
3 1 4 5 9 9 40 41
ok
ok
10 pythag_ancn
2 1 3 4 5
3 2 5 12 13
4 1 15 8 17
4 3 7 24 25
5 2 21 20 29
5 4 9 40 41
6 1 35 12 37
6 5 11 60 61
7 2 45 28 53
7 4 33 56 65
7 6 13 84 85
8 1 63 16 65
8 3 55 48 73
8 5 39 80 89
8 7 15 112 113
9 2 77 36 85
9 4 65 72 97
9 8 17 144 145
10 1 99 20 101
10 3 91 60 109
10 7 51 140 149
10 9 19 180 181
ok
You may also check:How to resolve the algorithm Catalan numbers/Pascal's triangle step by step in the TI-83 BASIC programming language
You may also check:How to resolve the algorithm SEDOLs step by step in the Go programming language
You may also check:How to resolve the algorithm Integer comparison step by step in the ColdFusion programming language
You may also check:How to resolve the algorithm Sorting algorithms/Counting sort step by step in the Elena programming language
You may also check:How to resolve the algorithm Character codes step by step in the PARI/GP programming language