Special pythagorean triplet: Difference between revisions
→{{header|Ring}}: various methods illustrated
(→{{header|Ring}}: illustrating straightforward method vs. faster method.) |
(→{{header|Ring}}: various methods illustrated) |
||
Line 820:
=={{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>tf = 1000 # time factor adjustment for different Ring versions
? "working..."
? "turtle method:" # 3 nested loops is not a good approach,
# even when cheating by cherry-picking the loop start/end points...
st = clock()
for
if
next
? "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
st = clock()
for a = 1 to 1000
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,
# cached some vars that didn't need recalcs over and over
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
b =
if b % (
next
b /= (
? "a = " + a + " b = " + b + " c = " + (
? "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
see "done..."</lang>
{{out}}
<pre>working...
a = 200 b = 375 c = 425
Elapsed time =
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:
a = 200 b = 375 c = 425
Elapsed time = 0.
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>
| |||