午後のひとときに、昨日上げた正の約数の総和を求めるアルゴリズムについて、プログラミングしてみた。
仮に名前を付けるとして、素因数分解法、五角数法としましょうか。
ただ、このままやってしまうと五角数法が明らかに不利になるので、ある数mまでのリストを表示させるようにしました。
これで互角の戦いを見せてくれるといいのですが、どうなるでしょうか。
素因数分解法：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main(int argc, char *argv[])
{
int m,n,i,end,prime,power,sum,product;
m = 10;
if ( argc == 2 ) {
m = atoi(argv[1]);
if ( m < 10 ) {
m = 10;
}
if ( m > 1000000 ) {
m = 1000000;
}
}
for (i=1; i<=m; i++) {
n = i;
end = sqrt((double)n)+1;
product = 1;
prime = 2;
power = 1;
sum = 1;
while ( n%prime == 0 ) {
n /= prime;
power *= prime;
sum += power;
}
product *= sum;
prime = 3;
while ( prime < end ) {
power = 1;
sum = 1;
while ( n%prime == 0 ) {
n /= prime;
power *= prime;
sum += power;
}
product *= sum;
prime += 2;
}
if ( n > 1 ) {
product *= 1+n;
}
printf("S(%d)=%d\n",i,product);
}
return EXIT_SUCCESS;
}
五角数法：
#include <stdio.h>
#include <stdlib.h>
#define MAX 100000
int s[MAX+1];
int main(int argc, char *argv[])
{
int n,m,i,j,k,sign;
m = 10;
if ( argc == 2 ) {
m = atoll(argv[1]);
if ( m < 10 ) {
m = 10;
}
if ( m > MAX ) {
m = MAX;
}
}
s[1] = 1;
s[2] = 3;
s[3] = 4;
printf("S(1)=1\nS(2)=3\nS(3)=4\n");
for (i=4; i<=m; i++) {
s[0] = i;
s[i] = 0;
sign = +1;
n = 1;
do {
j = n*(3*n-1)/2;
k = n*(3*n+1)/2;
if ( i >= j ) s[i] += sign*s[i-j];
if ( i >= k ) s[i] += sign*s[i-k];
n++;
sign *= -1;
} while ( k < i );
printf("S(%d)=%d\n",i,s[i]);
}
return EXIT_SUCCESS;
}
いつものことながら、C言語です。
五角数法のほうが10行程度短くコーディング出来ましたが、ほぼ大差ないかなと思います。
かれこれ35年くらい前、プログラマのバイトでは、1行10円とかだったから、これ2つで1000円くらいは貰えて、晩御飯がちょっとリッチになったりしたかな。
まぁ、それはおいておいて。
プログラムの速度的なものでいうと、数が少ないうちは大差ないですが、数を増やすと圧倒的に素因数分解のほうが倍くらい速かったです。
更に言えば、素因数分解法であれば、今回は素数として、2、それ以降は3以上の奇数で探索したが、素数として2、3、とやって、それ以降は6n－1型、6n＋1型で探索すれば、もう少し速度は速くなったりする余地がある。
まぁ、これもどこまでやるかということになるんだが、やりすぎても対して速くならなかったりもするので、ほどほどに。
五角数法はこれ以上の速度が見込める枝刈りは無いかなと思う。
逆に、五角数法を再帰処理でやろうとすると、例えばS(360)を計算するには、S(360－1)を呼び出すことから解るように、S(359)もS(359－1)を呼び出すわけで、なんだかんだ全部呼び出すことが解っているし、S(360－2)、S(350－5)、S(350－7)、…と呼び出すわけで、まったく数値の変わらない計算を何度も呼び出すことが解りきっています。
つまり、再帰処理は一見するとコード的には簡単に記述は出来ますが、速度は見込めないということが容易に解ります。
そういう意味もあって、配列に格納して、同じ計算を何度もさせないということにしているとも言えます。
もし、上記プログラムをコンパイルして、メモリーが足りないといったことになりましたら、MAXの値を減らして試してみてください。
そもそも論なんだが、正の約数の総和のリストが必要になるケースがあるのか？って思ってしまうが、まぁそれをいったらおしまいなので、そこは目をつむりましょうかね。
素因数分解法は、何を計算しているのか、コードを追えばなんとなく解るんだけれども、五角数法は、コードを追っても、不明な計算式があるので、それが解らなければ、何を求めているのかも解らないですね。
方法論として、複数あるってのは、とても有意義だと思うんですよね。
どちらのプログラムを使っても結果は同じですが、とりあえず100を与えた結果は以下の通りです。
S(1)=1
S(2)=3
S(3)=4
S(4)=7
S(5)=6
S(6)=12
S(7)=8
S(8)=15
S(9)=13
S(10)=18
S(11)=12
S(12)=28
S(13)=14
S(14)=24
S(15)=24
S(16)=31
S(17)=18
S(18)=39
S(19)=20
S(20)=42
S(21)=32
S(22)=36
S(23)=24
S(24)=60
S(25)=31
S(26)=42
S(27)=40
S(28)=56
S(29)=30
S(30)=72
S(31)=32
S(32)=63
S(33)=48
S(34)=54
S(35)=48
S(36)=91
S(37)=38
S(38)=60
S(39)=56
S(40)=90
S(41)=42
S(42)=96
S(43)=44
S(44)=84
S(45)=78
S(46)=72
S(47)=48
S(48)=124
S(49)=57
S(50)=93
S(51)=72
S(52)=98
S(53)=54
S(54)=120
S(55)=72
S(56)=120
S(57)=80
S(58)=90
S(59)=60
S(60)=168
S(61)=62
S(62)=96
S(63)=104
S(64)=127
S(65)=84
S(66)=144
S(67)=68
S(68)=126
S(69)=96
S(70)=144
S(71)=72
S(72)=195
S(73)=74
S(74)=114
S(75)=124
S(76)=140
S(77)=96
S(78)=168
S(79)=80
S(80)=186
S(81)=121
S(82)=126
S(83)=84
S(84)=224
S(85)=108
S(86)=132
S(87)=120
S(88)=180
S(89)=90
S(90)=234
S(91)=112
S(92)=168
S(93)=128
S(94)=144
S(95)=120
S(96)=252
S(97)=98
S(98)=171
S(99)=156
S(100)=217
ではでは