Hamming numbers: Difference between revisions
→a fast alternative: Pascal - added a non-duplicating, logarithmic estimation version...
(→{{header|F#}}: fix heading, as suggested on the Count examples/Full list/Tier 4 talk page) |
GordonBGood (talk | contribs) (→a fast alternative: Pascal - added a non-duplicating, logarithmic estimation version...) |
||
Line 7,897:
real 0m17.328s
user 0m17.310s</pre>
===Alternate Using Non-Duplicates Logarithmic Estimation Ordering===
The above is not a true sequence of Hamming numbers as it doesn't generate an iteration or enumeration of the numbers where each new value is generated from the accumulated state of all the generated numbers up to that point, but rather regenerates all the previous values very inefficiently for each new value, and thus does not have a linear execution complexity with number of generated values. Much more elegant solutions are those using functional programming paradigms, but as Pascal is by no means a functional language, lacking many of the requirements of functional programming such as closure functions to be functional and being difficult (although not impossible) to emulate those functions using classes/objects, the following code implements an imperative version of the non-duplicating Hamming sequence which also saves both time and space in not processing the duplicates (for instance, with two times three already accounted for, there is no need to process three times two); as well, since there is no standard "infinite" precision integer library for Pascal so that numbers larger than 64-bit can't easily be handled, the following code uses the "triplet" method and does the sorting based on a logarithmic estimation of the multiples:
<lang pascal>{$OPTIMIZATION LEVEL4}
program Hammings(output);
{$mode objfpc}
uses Math, SysUtils;
const
lb22 : Double = 1.0; (* log base 2 of 2 *)
lb23 : Double = 1.58496250072115618147; (* log base 2 of 3 *)
lb25 : Double = 2.32192809488736234781; (* log base 2 of 5 *)
type
TLogRep = record
lr : Double;
x2, x3, x5 : Word;
end;
const oneLogRep : TLogRep = (lr:0.0; x2:0; x3:0; x5:0);
function LogRepMult2(lr : TLogRep) : TLogRep;
begin
Result := lr;
Result.lr := lr.lr + lb22;
Result.x2 := lr.x2 + 1
end;
function LogRepMult3(lr : TLogRep) : TLogRep;
begin
Result := lr;
Result.lr := lr.lr + lb23;
Result.x3 := lr.x3 + 1
end;
function LogRepMult5(lr : TLogRep) : TLogRep;
begin
Result := lr;
Result.lr := lr.lr + lb25;
Result.x5 := lr.x5 + 1
end;
function LogRep2QWord(lr : TLogRep) : QWord;
function xpnd(x : Word; m : QWord) : QWord;
var mlt : QWord;
begin
mlt := m;
Result := 1;
while x > 0 do
begin
if x and 1 > 0 then Result := Result * mlt;
mlt := mlt * mlt; x := x shr 1
end
end;
begin
Result := xpnd(lr.x2, 2) * xpnd(lr.x3, 3) * xpnd(lr.x5, 5)
end;
type
TLogReps = array of TLogRep;
THammings = class
private
FCurrent : TLogRep;
FBA, FMA : TLogReps;
Fnxt2, Fnxt3, Fnxt5, Fmrg35 : TLogRep;
FBb, FBe, FMb, FMe : Integer;
public
constructor Create;
function GetEnumerator : THammings;
function MoveNext : Boolean;
property Current : TLogRep read FCurrent;
end;
constructor THammings.Create;
begin
inherited Create;
FCurrent := oneLogRep; FCurrent.lr := -1.0;
SetLength(FBA, 4); SetLength(FMA, 4);
Fnxt5 := LogRepMult5(oneLogRep);
Fmrg35 := LogRepMult3(oneLogRep);
Fnxt3 := LogRepMult3(Fmrg35);
Fnxt2 := LogRepMult2(oneLogRep);
FBb := 0; FBe := 0; FMb := 0; FMe := 0
end;
function THammings.GetEnumerator : THammings;
begin
Result := Self
end;
function THammings.MoveNext : Boolean;
var blen, mlen, i, j : Integer;
begin
if FCurrent.lr < 0.0 then FCurrent.lr := 0.0 else
begin
blen := Length(FBA);
if FBb >= blen shr 1 then
begin
i := 0;
for j := FBb to FBe - 1 do
begin
FBA[i] := FBA[j]; Inc(i)
end;
FBe := FBe - FBb; FBb := 0
end;
if FBe >= blen then SetLength(FBA, blen shl 1);
if Fnxt2.lr < Fmrg35.lr then
begin
FCurrent := Fnxt2; FBA[FBe] := FCurrent;
Fnxt2 := LogRepMult2(FBA[FBb]); Inc(FBb)
end
else
begin
mlen := Length(FMA);
if FMb >= mlen shr 1 then
begin
i := 0;
for j := FMb to FMe - 1 do
begin
FMA[i] := FMA[j]; Inc(i)
end;
FMe := FMe - FMb; FMb := 0
end;
if FMe >= mlen then SetLength(FMA, mlen shl 1);
if Fmrg35.lr < Fnxt5.lr then
begin
FCurrent := Fmrg35; FMA[FMe] := FCurrent;
Fnxt3 := LogRepMult3(FMA[FMb]); Inc(FMb)
end
else
begin
FCurrent := Fnxt5; FMA[FMe] := FCurrent;
Fnxt5 := LogRepMult5(Fnxt5)
end;
if Fnxt3.lr < Fnxt5.lr then Fmrg35 := Fnxt3 else Fmrg35 := Fnxt5;
FBA[FBe] := FCurrent; Inc(FMe)
end;
Inc(FBe)
end;
Result := True
end;
var elpsd : QWord;
count : Integer;
h : TLogRep;
begin
write('The first 20 Hamming numbers are: ');
count := 0;
for h in THammings.Create do
begin
Inc(count);
if count > 20 then break;
write(' ', LogRep2QWord(h));
end;
writeln('.');
count := 1;
for h in THammings.Create do
begin
Inc(count);
if count > 1691 then break;
end;
writeln('The 1691st Hamming number is ', LogRep2QWord(h), '.');
elpsd := GetTickCount64;
count := 1;
for h in THammings.Create do
begin
Inc(count);
if count > 1000000 then break;
end;
elpsd := GetTickCount64 - elpsd;
writeln('The millionth Hamming number is approximately ', 2.0**h.lr, '.');
write('The millionth Hamming number is ');
writeln('2^', h.x2, ' * 3^', h.x3, ' * 5^', h.x5, '.');
writeln('This last took ', elpsd, ' milliseconds.')
end.</lang>
{{out}}
<pre>The first 20 Hamming numbers are: 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36.
The 1691st Hamming number is 2125764000.
The millionth Hamming number is approximately 5.19312780448555124533E+0083.
The millionth Hamming number is 2^55 * 3^47 * 5^64.
This last took 13 milliseconds.</pre>
The above was as run on a modern Intel CPU at 4 GHz.
Note that as the millionth Hamming number would have 83 decimal digits and the largest standard 64-bit value that is easily expressed in standard Pascal is only about 19 decimal digits, the millionth Hamming number is expressed in terms of its "triplet".
===a fast alternative ===
The Pascal code above is by far slower.Easily to use for smooth-3 .. smooth-37.
| |||