Special pythagorean triplet: Difference between revisions

Content added Content deleted
(→‎{{header|Ring}}: illustrating straightforward method vs. faster method.)
(→‎{{header|Ring}}: various methods illustrated)
Line 820: Line 820:


=={{header|Ring}}==
=={{header|Ring}}==
Various algorithms presented, some are quite fast. Timings are from Tio.run. On the desktop of a core i7-7700 @ 3.60Ghz, it goes about 6.5 times faster.
<lang ring>
<lang ring>tf = 1000 # time factor adjustment for different Ring versions

? "working..."
? "working..."


? "turtle method:" # 3 nested loops is not a good approach,
? "brute force method:"
# even when cheating by cherry-picking the loop start/end points...
time1 = clock()
st = clock()
for a = 1 to 998

aa = a * a
for b = a + 1 to 999
for a = 100 to 400
bb = aa + b * b
for b = 200 to 800
c = 1000 - a - b
for c = b to 1000 - a - b
if bb = c * c
if a + b + c = 1000
? "a = " + a + " b = " + b + " c = " + c
if a * a + b * b = c * c exit 3 ok
exit 2
ok
ok
next
next
next
next
next
time2 = clock()
et = clock() - st
? "a = " + a + " b = " + b + " c = " + c
? "Elapsed time = " + et / (tf * 1000) + " s" + nl


? "brutally forced method:" # eliminating the "c" loop speeds it up a bit
? "Elapsed time = " + (time2 - time1) / 1000 + " ms"
st = clock()


for a = 1 to 1000
? "quick method:"
for b = a to 1000
c = 1000 - a - b
if a * a + b * b = c * c exit 2 ok
next
next
et = clock() - st
? "a = " + a + " b = " + b + " c = " + c
? "Elapsed time = " + et / tf + " ms" + nl
# some basic info about this task:
p = 1000 pp = p * p >> 1 # perimeter, half of perimeter^2
maxc = ceil(sqrt(pp) * 2) - p # minimum c = 415 ceiling of ‭414.2135623730950488016887242097‬
maxa = (p - maxc) >> 1 # maximum a = 292, shorter leg will shrink
minb = p - maxc - maxa # minimum b = 293, longer leg will lengthen


? "polished brute force method:" # calculated realistic limits for the loops,
time1 = clock()
# cached some vars that didn't need recalcs over and over
n = 1000
n2 = n >> 1
st = clock()
minb = maxa + 1 maxb = p - maxc pma = p - 1
for a = 1 to maxa
aa = a * a
c = pma - minb
for b = minb to maxb
if aa + b * b = c * c exit 2 ok
c--
next
pma--
next
et = clock() - st
? "a = " + a + " b = " + b + " c = " + c
? "Elapsed time = " + et / tf + " ms" + nl
? "quick method:" # down to one loop, using some math insight
st = clock()
n2 = p >> 1
for a = 1 to n2
for a = 1 to n2
b = n * (n2 - a)
b = p * (n2 - a)
if b % (n - a) = 0 exit ok
if b % (p - a) = 0 exit ok
next
next
b /= (n - a)
b /= (p - a)
? "a = " + a + " b = " + b + " c = " + (n - a - b)
? "a = " + a + " b = " + b + " c = " + (p - a - b)
time2 = clock()
et = clock() - st
? "Elapsed time = " + et / tf + " ms" + nl

? "even quicker method:" # generate primitive Pythagorean triples,
# then scale to fit the actual perimeter
st = clock()
p = 1000 md = 1 ms = 1
for m = 1 to 4
nd = md + 2 ns = ms + nd
for n = m + 1 to 5
if p % (((n * m) + ns) << 1) = 0 exit 2 ok
nd += 2 ns += nd
next
md += 2 ms += md
next
et = clock() - st
a = n * m << 1 b = ns - ms c = ns + ms d = p / (((n * m) + ns) << 1)
? "a=" + a * d + " b=" + b * d + " c=" + c * d
? "Elapsed time = " + et / tf + " ms" + nl

? "alternate method:" # only uses addition / subtraction inside the loops.
# makes a guess, then tweaks the guess until correct
st = clock()
a = maxa b = minb
g = p * (a + b) - a * b # guess
while g != pp
if pp > g
b++ g += p - a # step "b" only when the "a" step went too far
ok
a-- g -= p - b # step "a" on every iteration
end
et = clock() - st
? "a=" + a + " b=" + b + " c=" + (p - a - b)
? "Elapsed time = " + et / tf + " ms" + nl


? "Elapsed time = " + (time2 - time1) / 1000 + " ms"
see "done..."</lang>
see "done..."</lang>
{{out}}
{{out}}
Quicker method is about 1000x faster.
<pre>working...
<pre>working...
brute force method:
turtle method:
a = 200 b = 375 c = 425
a = 200 b = 375 c = 425
Elapsed time = 927.21 ms
Elapsed time = 13.36 s

brutally forced method:
a = 200 b = 375 c = 425
Elapsed time = 983.94 ms

polished brute force method:
a = 200 b = 375 c = 425
Elapsed time = 216.66 ms

quick method:
quick method:
a = 200 b = 375 c = 425
a = 200 b = 375 c = 425
Elapsed time = 0.90 ms
Elapsed time = 0.97 ms

even quicker method:
a=200 b=375 c=425
Elapsed time = 0.18 ms

alternate method:
a=200 b=375 c=425
Elapsed time = 0.44 ms

done...</pre>
done...</pre>