73 lines
3.7 KiB
C#
73 lines
3.7 KiB
C#
using System;
|
|
using System.Linq;
|
|
using System.Numerics;
|
|
|
|
namespace HammingFast {
|
|
|
|
class MainClass {
|
|
|
|
private static int[] _primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 };
|
|
|
|
public static BigInteger Big(int[] exponents) {
|
|
BigInteger val = 1;
|
|
for (int i = 0; i < exponents.Length; i++)
|
|
for (int e = 0; e < exponents[i]; e++)
|
|
val = val * _primes[i];
|
|
return val;
|
|
}
|
|
|
|
public static int[] Hamming(int n, int nprimes) {
|
|
var hammings = new int[n, nprimes]; // array of hamming #s we generate
|
|
var hammlogs = new double[n]; // log values for above
|
|
var primelogs = new double[nprimes]; // pre-calculated prime log values
|
|
var indexes = new int[nprimes]; // intermediate hamming values as indexes into hammings
|
|
var listheads = new int[nprimes, nprimes]; // intermediate hamming list heads
|
|
var listlogs = new double[nprimes]; // log values of list heads
|
|
for (int p = 0; p < nprimes; p++) {
|
|
listheads[p, p] = 1; // init list heads to prime values
|
|
primelogs[p] = Math.Log(_primes[p]); // pre-calc prime log values
|
|
listlogs[p] = Math.Log(_primes[p]); // init list head log values
|
|
}
|
|
for (int iter = 1; iter < n; iter++) {
|
|
int min = 0; // find index of min item in list heads
|
|
for (int p = 1; p < nprimes; p++)
|
|
if (listlogs[p] < listlogs[min])
|
|
min = p;
|
|
hammlogs[iter] = listlogs[min]; // that's the next hamming number
|
|
for (int i = 0; i < nprimes; i++)
|
|
hammings[iter, i] = listheads[min, i];
|
|
for (int p = 0; p < nprimes; p++) { // update each list head if it matches new value
|
|
bool equal = true; // test each exponent to see if number matches
|
|
for (int i = 0; i < nprimes; i++) {
|
|
if (hammings[iter, i] != listheads[p, i]) {
|
|
equal = false;
|
|
break;
|
|
}
|
|
}
|
|
if (equal) { // if it matches...
|
|
int x = ++indexes[p]; // set index to next hamming number
|
|
for (int i = 0; i < nprimes; i++) // copy each hamming exponent
|
|
listheads[p, i] = hammings[x, i];
|
|
listheads[p, p] += 1; // increment exponent = mult by prime
|
|
listlogs[p] = hammlogs[x] + primelogs[p]; // add log(prime) to log(value) = mult by prime
|
|
}
|
|
}
|
|
}
|
|
|
|
var result = new int[nprimes];
|
|
for (int i = 0; i < nprimes; i++)
|
|
result[i] = hammings[n - 1, i];
|
|
return result;
|
|
}
|
|
|
|
public static void Main(string[] args) {
|
|
foreach (int np in new int[] { 3, 4, 5 }) {
|
|
Console.WriteLine("{0}-Smooth:", _primes[np - 1]);
|
|
Console.WriteLine(string.Join(" ", Enumerable.Range(1, 20).Select(x => Big(Hamming(x, np)))));
|
|
Console.WriteLine(Big(Hamming(1691, np)));
|
|
Console.WriteLine(Big(Hamming(1000000, np)));
|
|
Console.WriteLine();
|
|
}
|
|
}
|
|
}
|
|
}
|