Search
As of October, 2016, Embarcadero is offering a free release
of Delphi (Delphi
10.1 Berlin Starter Edition ). There
are a few restrictions, but it is a welcome step toward making
more programmers aware of the joys of Delphi. They do say
"Offer may be withdrawn at any time", so don't delay if you want
to check it out. Please use the
feedback link to let
me know if the link stops working.
Support DFF - Shop
If you shop at Amazon anyway, consider
using this link.
We receive a few cents from each
purchase. Thanks
Support DFF - Donate
If you benefit from the website, in terms of
knowledge, entertainment value, or something otherwise useful,
consider making a donation via PayPal to help defray the
costs. (No PayPal account necessary to donate via credit
card.) Transaction is secure.
Mensa®
Daily Puzzlers
For over 15 years
Mensa Page-A-Day calendars have provided several puzzles a year
for my programming pleasure. Coding "solvers" is most fun,
but many programs also allow user solving, convenient for "fill
in the blanks" type. Below are Amazon links to the
two most recent years.
Mensa®
365 Puzzlers Calendar 2017
Mensa®
365 Puzzlers Calendar 2018
(Hint: If you can
wait, current year calendars are usually on sale in January.)
Contact
Feedback:
Send an
e-mail with your comments about this program (or anything else).
|
| |
By definition, the Greatest Common Divisor (GCD) of two positive integers is the
largest integer which divides both integers exactly.
2000 years ago Mr. Euclid developed, or a least published, an algorithm
for finding the GCD of two numbers. His version was strictly geometrical
and depends on the fact that the the GCD of any two numbers a and b
(with a not less than b) is the same as the GCD of the b
and the remainder when a is divided by b.
|
Algebra hadn't been invented when Euclid published his
technique, but an algebraic proof looks like this:
Take any two positive integers a and
b with b smaller
than a. Euclid noted that there are
integers r and
q such that a=qb
+ r. (Just
divide b into a, then
q is the quotient and
r
is the remainder.)
Any common factor, N, of
b and r divides
a exactly : (N divides
b so it divides qb and it
divides r so it divides the sum,
qb +
r, which
is a of course.)
Any common factor, M, of
a and
b divides
r exactly
: (r
=a-qb so
r/M=a/M-qb/M.
a/M
is an integer and qb/M is an integer so their difference,
r/M, is
an integer so M divides r.)
Note that all of the N's are
M's and all the
M's are N's
so the largest N must equal the largest M. In other
words: GCD(a,b) =
GCD(b,r). b is less than
a
and r is less than
b so we can repeat these steps substituting
b
for a and r for
b until r becomes
0.
the previous step has a=qb+0 and
b is the desired
GCD.
|
Here's an example of the algorithm in action
Find the GCD of 2322 and 654. Let a = 2322, b = 654
2322/654 =3. Remainder = 360 so gcd(2322, 654) = gcd(654, 360)
654/360 = 1, Remainder = 294 so gcd(654, 360) = gcd(360, 294)
360/294 = 1, Remainder = 66 so gcd(360, 294) = gcd(294, 66)
294/ 66 = 4, Remainder = 30 so gcd(294, 66) = gcd(66, 30)
66/30 = 2, Reaminder = 6 so gcd(66, 30) = gcd(30, 6)
30/6 = 5, Remainder 0 so gcd(30, 6) = 6
Therefore, gcd(2322,654) = 6.
Check http://www.cut-the-knot.com/blue/Euclid.html
for more good info. Program PiCalc2 on this
site estimates of Pi by calculating the GCD of pairs of random integers.
A Sample Implementation in Delphi
Function
gcd(a,b:integer):integer;
{return greatest common denominator of a and b}
var g,z:integer;
begin
g:=b;
while g<>0 do
begin
z:=a mod g;
a:=g;
g:=z;
end;
result:=a;
end;
|
