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 a = 100 to 400 |
|||
for b = 200 to 800 |
|||
for c = b to 1000 - a - b |
|||
if |
if a + b + c = 1000 |
||
if a * a + b * b = c * c exit 3 ok |
|||
ok |
|||
next |
|||
next |
|||
next |
next |
||
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 |
|||
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 = |
b = p * (n2 - a) |
||
if b % ( |
if b % (p - a) = 0 exit ok |
||
next |
next |
||
b /= ( |
b /= (p - a) |
||
? "a = " + a + " b = " + b + " c = " + ( |
? "a = " + a + " b = " + b + " c = " + (p - a - b) |
||
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... |
||
turtle method: |
|||
a = 200 b = 375 c = 425 |
a = 200 b = 375 c = 425 |
||
Elapsed time = |
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. |
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> |
||