素数の振りして素数に非ず
- このフォーラムに新規トピックを投稿できます
- このフォーラムではゲスト投稿が許可されています
投稿ツリー
-
素数の振りして素数に非ず (東 遥, 2017/4/16 21:45)
-
Re: 素数の振りして素数に非ず (粒子, 2017/4/17 4:14)
-
Re: 素数の振りして素数に非ず (YMN, 2017/4/17 20:47)
-
Re: 素数の振りして素数に非ず (FarSeer08, 2017/4/18 3:23)
-
Re: 素数の振りして素数に非ず (YMN, 2017/4/18 19:41)
-
Re: 素数の振りして素数に非ず (FarSeer08, 2017/4/23 16:49)
-
十進BASICの有理数モード (YMN, 2017/4/27 20:29)
-
Re: 十進BASICの有理数モード (YMN, 2017/4/27 20:31)
-
Re: 十進BASICの有理数モード (YMN, 2017/4/28 21:06)
-
Re: 十進BASICの有理数モード (YMN, 2017/5/8 22:51)
-
ベタベタの回答 (FarSeer08, 2017/5/21 22:49)
-
Re: 十進BASICの有理数モード (FarSeer08, 2017/6/2 19:53)
-
Re: 十進BASICの有理数モード (YMN, 2017/6/3 21:24)
-
多桁計算のテケトーな速度比較 (FarSeer08, 2017/6/4 6:58)
-
Re: 多桁計算のテケトーな速度比較 (Chryso, 2018/1/17 7:28)
-
宇宙人テスト (YMN, 2018/1/18 23:16)
-
Re: 宇宙人テスト (YMN, 2018/2/10 14:16)
東 遥
投稿数: 4359

素数。数字の原子とも言われるアレ。
ぇぇ、意外と使うんですよ、乱数を自作しなければならない時なんかに。ぇ? rnd関数とかrandom関数とか使えばよいではないか、って? ぃゃ、まぁ、そうゆうのが使える高級環境なら宜しいですけどね? 除算は兎も角乗算だって自分でチクチクとやらなければならない時だってあるんですよ、足したりなんだりして。
まぁ、それはそれとしてですな。皆さん、素数と思いますとどんなのを思い起こされますか? 直ぐに思い浮かべる素数の数でその人の人生の豊かさが判るというお話も御座いませんが、ぇぇ、例えば千の前後、或いは万の前後では、如何です?
「1001の素数じゃないのかよ具合はそんじょそこらの自然数では太刀打ちできない」「7は野放しにしちゃいけない」「2とか5は独占欲が強い」
ぃゃ、ぃゃぃゃ、、独占欲ですか(笑)。或いは3は芸達者というものなのかどうか。ぇぇ、一頃3の倍数でなんとかになる、というのも御座いましたし。
では問題。1000、10000、100000、に最も近い、具体的には、それぞれの値より小さくて最も近いもの、また、それぞれの値より大きくて最も近いもの、計6個は、なんでしょうか。
意外と、ね。因みに 1001, 10001, 100001 は駄目です。ていうか、どんな素因数分解できるやら暗算ではできそうもない。尚、2^N の前後、と申し上げない所は私の良心だと、思っていただければ幸いです。
あ、勿論既存のツールとかアプリとかは無しで、できれば肉筆筆算で、とも存じましたが、それはそれであんまりなので、自らプログラムして、或いはEXCELのマクロを使うとかで、手を動かして求めて戴ければと存ずる次第。
ぇぇ、意外と使うんですよ、乱数を自作しなければならない時なんかに。ぇ? rnd関数とかrandom関数とか使えばよいではないか、って? ぃゃ、まぁ、そうゆうのが使える高級環境なら宜しいですけどね? 除算は兎も角乗算だって自分でチクチクとやらなければならない時だってあるんですよ、足したりなんだりして。
まぁ、それはそれとしてですな。皆さん、素数と思いますとどんなのを思い起こされますか? 直ぐに思い浮かべる素数の数でその人の人生の豊かさが判るというお話も御座いませんが、ぇぇ、例えば千の前後、或いは万の前後では、如何です?
「1001の素数じゃないのかよ具合はそんじょそこらの自然数では太刀打ちできない」「7は野放しにしちゃいけない」「2とか5は独占欲が強い」
ぃゃ、ぃゃぃゃ、、独占欲ですか(笑)。或いは3は芸達者というものなのかどうか。ぇぇ、一頃3の倍数でなんとかになる、というのも御座いましたし。
では問題。1000、10000、100000、に最も近い、具体的には、それぞれの値より小さくて最も近いもの、また、それぞれの値より大きくて最も近いもの、計6個は、なんでしょうか。
意外と、ね。因みに 1001, 10001, 100001 は駄目です。ていうか、どんな素因数分解できるやら暗算ではできそうもない。尚、2^N の前後、と申し上げない所は私の良心だと、思っていただければ幸いです。
あ、勿論既存のツールとかアプリとかは無しで、できれば肉筆筆算で、とも存じましたが、それはそれであんまりなので、自らプログラムして、或いはEXCELのマクロを使うとかで、手を動かして求めて戴ければと存ずる次第。
投票数:0
平均点:0.00
返信する
粒子
投稿数: 992

37の3の倍数はゾロメになるというのがありますね。
世界のナベアツとかどうしているのでしょうか。
素数表を見たらだめなのでしょうか?
世界のナベアツとかどうしているのでしょうか。
素数表を見たらだめなのでしょうか?
投票数:0
平均点:0.00
返信する
YMN
投稿数: 1018

素因数分解のプログラムです。
101は素数ですが、それ以外は素数でない法則がありげです。
1001 7 11 13
10001 73 137
100001 11 9091
1000001 101 9901
10000001 11 909091
100000001 17 5882353
1000000001 7 11 13 19 52579
*ST
INPUT A
L=SQR(A)
L=INT(L)
T=A
FOR N=2 TO L
IF T MOD N=0 THEN T=T/N:PRINT N
IF T=1 THEN GOTO *ST
NEXT N
PRINT T
GOTO *ST
101は素数ですが、それ以外は素数でない法則がありげです。
1001 7 11 13
10001 73 137
100001 11 9091
1000001 101 9901
10000001 11 909091
100000001 17 5882353
1000000001 7 11 13 19 52579
投票数:0
平均点:0.00
返信する
FarSeer08
投稿数: 278

引用:
これは怪しいです。
素数かどうか調べるのには十分ですが、同じ素因数が複数あると十分に分解できないような……。
素因数分解のプログラムです。
これは怪しいです。
素数かどうか調べるのには十分ですが、同じ素因数が複数あると十分に分解できないような……。
投票数:0
平均点:0.00
返信する
YMN
投稿数: 1018

>素数かどうか調べるのには十分ですが、同じ素因数が複数あると十分に分解できないような……。
そうでした。
ということで作り直しました。
そうでした。
ということで作り直しました。
*LP1
INPUT A
*LP2
GOSUB *ST
IF T=1 OR A=T THEN PRINT:GOTO *LP1
A=T
GOTO *LP2
*ST
L=SQR(A)
L=INT(L)
T=A
FOR N=2 TO L
IF T MOD N=0 THEN T=T/N:PRINT N;:RETURN
NEXT N
IF T=A THEN PRINT T;
RETURN
投票数:0
平均点:0.00
返信する
FarSeer08
投稿数: 278

早速の改訂おつかれさまです。
と言うことで、10進BASICにしてみました。
前回(別スレ)は、Macで動くBASICということで検索して出てきたのを使っただけなので、「10進」は事務計算用でBCDかと思っていました。
本家ウェブサイトの説明を見ると、実際は違うらしく、開発者も数学の先生なので、「10進」なのは数学用途のためのようです。
なので、主目的はこういうことなのではないかと思います。
と言うことで、10進BASICにしてみました。
OPTION ARITHMETIC DECIMAL_HIGH
10 INPUT A
20 GOSUB 100
IF T=1 OR A=T THEN
PRINT
GOTO 10
END IF
LET A=T
GOTO 20
100 LET L=SQR(A)
LET L=INT(L)
LET T=A
FOR N=2 TO L
IF MOD(T , N) =0 THEN
LET T=T/N
PRINT N;
RETURN
END IF
NEXT N
IF T=A THEN PRINT T
RETURN
END
前回(別スレ)は、Macで動くBASICということで検索して出てきたのを使っただけなので、「10進」は事務計算用でBCDかと思っていました。
本家ウェブサイトの説明を見ると、実際は違うらしく、開発者も数学の先生なので、「10進」なのは数学用途のためのようです。
なので、主目的はこういうことなのではないかと思います。

投票数:0
平均点:0.00
返信する
YMN
投稿数: 1018

OPTION ARITHMETIC RATIONAL
Y=100
FOR X=1 TO 30
Y=Y*10
A=Y+1
PRINT A;
GOSUB 20
NEXT X
STOP
20 GOSUB 100
IF T=1 OR A=T THEN
RETURN
END IF
LET A=T
GOTO 20
100
LET L=INTSQR(A)
LET T=A
FOR N=2 TO L
IF MOD(T , N) =0 THEN
LET T=T/N
PRINT N;
RETURN
END IF
NEXT N
IF T=A THEN PRINT T
RETURN
END
十進BASICには超高精度の十進1000桁や有理数などのモードがあり、有理数モードでは少数ではなくて分数で数値が扱われ、長大な整数を扱うこともできます(整数の桁数はメモリが可能な限りだそうです)。
プログラムの先頭行は有理数モードにする宣言です。
有理数モードで10・・・01パターンの系列の素因数分解を行うプログラムです。
すごく時間がかかるので途中で止めましたが、その結果です。
1001 7 11 13
10001 73 137
100001 11 9091
1000001 101 9901
10000001 11 909091
100000001 17 5882353
1000000001 7 11 13 19 52579
10000000001 101 3541 27961
100000000001 11 11 23 4093 8779
1000000000001 73 137 99990001
10000000000001 11 859 1058313049
100000000000001 29 101 281 121499449
1000000000000001 7 11 13 211 241 2161 9091
10000000000000001 353 449 641 1409 69857
100000000000000001 11 103 4013 21993833369
1000000000000000001 101 9901 999999000001
10000000000000000001 11 909090909090909091
100000000000000000001 73 137 1676321 5964848081
1000000000000000000001 7 7 11 13 127 2689 459691 909091
10000000000000000000001 89 101 1052788969 1056689261
100000000000000000000001 11 47 139 2531 549797184491917
1000000000000000000000001 17 5882353 9999999900000001
10000000000000000000000001 11 251 5051 9091 78875943472201
投票数:0
平均点:0.00
返信する
YMN
投稿数: 1018

OPTION ARITHMETIC RATIONAL
Y=100
FOR X=4 TO 1000
Y=Y*10
A=Y+1
PRINT X;
IF X<10 THEN PRINT A;
GOSUB 100
NEXT X
STOP
100
LET L=INTSQR(A)
LET T=A
FOR N=2 TO L
IF MOD(T , N) =0 THEN
PRINT N
RETURN
END IF
NEXT N
PRINT "S"
RETURN
END
10・・・01のパターンが素数かどうかだけを調べるには素因数分解する必要はなく、(小さい方から調べて)約数がひとつでもあればそこで切り上げてしまうプログラムにしました。
4ケタから1000桁まで調べるプログラムです。
やたらと大きな数の10・・・01を表示しても嵩張るばかりですので、10桁以上は表示しないようにして、桁数と約数だけ表示するにしました。
結構な時間がかかって1000桁まで調べましたが、素数はひとつもありませんでした(もちろんそれでは無いことの示唆にはなっても証明にはなりません)。
以下は100桁までのその結果です。
65桁で約数が極端に大きく、ここで多大な時間がかかりました。
4 1001 7
5 10001 73
6 100001 11
7 1000001 101
8 10000001 11
9 100000001 17
10 7
11 101
12 11
13 73
14 11
15 29
16 7
17 353
18 11
19 101
20 11
21 73
22 7
23 89
24 11
25 17
26 11
27 101
28 7
29 73
30 11
31 61
32 11
33 19841
34 7
35 101
36 11
37 73
38 11
39 101
40 7
41 17
42 11
43 29
44 11
45 73
46 7
47 101
48 11
49 97
50 11
51 101
52 7
53 73
54 11
55 101
56 11
57 17
58 7
59 101
60 11
61 73
62 11
63 101
64 7
65 1265011073
66 11
67 89
68 11
69 73
70 7
71 29
72 11
73 17
74 11
75 101
76 7
77 73
78 11
79 101
80 11
81 353
82 7
83 101
84 11
85 73
86 11
87 101
88 7
89 17
90 11
91 61
92 11
93 73
94 7
95 101
96 11
97 193
98 11
99 29
100 7
投票数:0
平均点:0.00
返信する
YMN
投稿数: 1018

OPTION ARITHMETIC RATIONAL
INPUT PROMPT "START ":S
INPUT PROMPT "ADD ":A
LET E=S+A
FOR X=S TO E
GOSUB 100
NEXT X
PRINT
STOP
100
LET L=INTSQR(X)
FOR N=2 TO L
IF MOD(X , N) =0 THEN RETURN
NEXT N
PRINT X;
RETURN
END
素数に関するバリエーションということで、作ってみました。
整数S,Aを入力し、S~S+Aまでの間にある素数を全て表示します。
整数の桁数は無制限ですが、あまり数が大きくなると処理時間が極端にかかります。
投票数:0
平均点:0.00
返信する
YMN
投稿数: 1018

1000・・・0001のパターンで素数があるか、コンピュータをガラガラ回して引き続き調べました。
素数でないものが続きましたが、1025桁(つまり間の0が23個)で長大な時間がかかりメモリが足らなくなったのかハングアップしてしまいました。
素数なのか、あるいは素数ではないけれどやたらと約数が大きいのかどちらかということになります。
プログラムは1025桁の対象数に対して、割り切れるか否か調べる数をひとつづつ増やしていくものですが、何時間もかかってハングアップするとき、その数はまだ10桁でした。
もし素数で、仮にハングアップしないとしても、この方式では検証に現実的でない時間がかかることになりそうです。
素数でないものが続きましたが、1025桁(つまり間の0が23個)で長大な時間がかかりメモリが足らなくなったのかハングアップしてしまいました。
素数なのか、あるいは素数ではないけれどやたらと約数が大きいのかどちらかということになります。
プログラムは1025桁の対象数に対して、割り切れるか否か調べる数をひとつづつ増やしていくものですが、何時間もかかってハングアップするとき、その数はまだ10桁でした。
もし素数で、仮にハングアップしないとしても、この方式では検証に現実的でない時間がかかることになりそうです。
投票数:0
平均点:0.00
返信する
FarSeer08
投稿数: 278

有理数モードというのは、ヘルプを見てもモヤッとしたことしか載っていないので使わなかったのですが、ウェブのFAQに使い分けについては明確に書かれていますね。
元の問題を解く材料は全部出ていますが答えそのものがないので、一応ベタベタのプログラムを貼っておきます。
元の問題を解く材料は全部出ていますが答えそのものがないので、一応ベタベタのプログラムを貼っておきます。
OPTION ARITHMETIC RATIONAL
10 INPUT num
LET n = num
20!'
CALL factor(n, f)
IF f = 1 THEN!' Call by reference
PRINT num; " は素数です"
GOTO 10
ELSE
PRINT num; " は合成数です("; f; "で割り切れて商は"; n; ")"
LET n = num
CALL adumaQ(n)
GOTO 10
END IF
END
EXTERNAL SUB factor(n, f)
OPTION ARITHMETIC RATIONAL
LET m=INTSQR(n)
FOR i=2 TO m
IF MOD(n, i) = 0 THEN
LET f = i
LET n = n / i
EXIT SUB
END IF
NEXT i
LET f = 1
END SUB
!'
EXTERNAL SUB adumaQ(n)
OPTION ARITHMETIC RATIONAL
LET N_NEIGHBOR = 3
IF n <= 2 THEN
EXIT SUB
END IF
LET d = 0
PRINT " 隣接する素数は近い順に(大小"; N_NEIGHBOR; "つまで)"
PRINT " 大きな方は"
FOR i = 1 TO N_NEIGHBOR
LET f = n
DO WHILE f > 1
LET d = d + 1
CALL factor(n+d, f)
LOOP
PRINT " "; n+d
NEXT I
LET d = 0
PRINT " 小さな方は"
FOR i = 1 TO N_NEIGHBOR
LET f = n
DO WHILE f > 1
LET d = d + 1
CALL factor(n-d, f)
LOOP
IF n-d >= 2 THEN
PRINT " "; n-d
ELSE
PRINT " もうありません"
END IF
NEXT I
END SUB
? 1001
1001 は合成数です( 7 で割り切れて商は 143 )
隣接する素数は近い順に(大小 3 つまで)
大きな方は
1009
1013
1019
小さな方は
997
991
983
? 10001
10001 は合成数です( 73 で割り切れて商は 137 )
隣接する素数は近い順に(大小 3 つまで)
大きな方は
10007
10009
10037
小さな方は
9973
9967
9949
? 100001
100001 は合成数です( 11 で割り切れて商は 9091 )
隣接する素数は近い順に(大小 3 つまで)
大きな方は
100003
100019
100043
小さな方は
99991
99989
99971
投票数:0
平均点:0.00
返信する
FarSeer08
投稿数: 278

引用:
ちょっと観察してみましょう。
同じような数が頻繁に出てきて入り乱れているようですが……よくみると、7, -, 11, -, 11, -, 7, ... などのパターンの繰り返しも見つかります。パターンを見るには、1つ前の素因数分解のプログラムの出力の方が良さそうです。
その前に表記を簡潔にするため、数列を


で定義します(ついでに、想定されている規則に[たぶん]反せずに含められる 11 も 101 の前に入っています)。
素因数分解の出力では、後のプログラムの出力で( 7 が先に見つかるので) 隠れていた 11 も出ています。



:
奇数番項(2k + 1, k = 0, 1, 2, ...)はすべて、11 を素因数として含んでいます。
計算機まかせではなく筆算でもしてみると帰納的にわかります。
→奇数番項はすべて合成数であり、素数が含まれる可能性が残るのは、偶数番項で構成される部分数列内に絞られて「大きさ」は半分に。
(追記:最初の 11, 101 は素数ですけど、ここでは他の素数を探すと言う意味で)
同様にして



:
(4k + 2, k = 0, 1, 2, ...)番項はすべて、101 を素因数として含んでいます。
計算機まかせではなく筆算でもしてみると帰納的にわかります。
→(4k + 2, k = 0, 1, 2, ...)番項はすべて合成数です。
{4k + 2| k = 0, 1, 2, ...}は、4 で割ると 2 余る自然数の集合です。前のステップで、素数候補は偶数番項に絞られましたが、このステップで 4 で割ると 2 余る数(当然、偶数)もアウトのため、素数が含まれる可能性が残るのは、第(4 の倍数)項だけになりました。
同様にして



:
(8k + 4, k = 0, 1, 2, ...)番項はすべて、73 を素因数として含んでいます。
計算機まかせではなく筆算でもしてみると帰納的にわかります。
→(8k + 4, k = 0, 1, 2, ...)番項はすべて合成数です。
{8k + 4| k = 0, 1, 2, ...}は、8 で割ると 4 余る自然数の集合です。前のステップで、素数候補は(4の倍数)番項に絞られましたが、このステップで 8 で割ると 4 余る数(当然、4 の倍数)もアウトのため、素数が含まれる可能性が残るのは、ここまでで第(8 の倍数)項だけということになりました……
ところで、YMNさんが見つけだした「凶悪」な数(最小の素因数が、1265011073である数)は、ここでの定義でいうと(元発言とでは 1 ずれるので)第64項です。 これは第(16 の倍数)項の 1 つです。
#6/3 追記で補足
4ケタから1000桁まで調べるプログラムです。
(中略)
65桁で約数が極端に大きく、ここで多大な時間がかかりました。
(中略)
65 1265011073
ちょっと観察してみましょう。
同じような数が頻繁に出てきて入り乱れているようですが……よくみると、7, -, 11, -, 11, -, 7, ... などのパターンの繰り返しも見つかります。パターンを見るには、1つ前の素因数分解のプログラムの出力の方が良さそうです。
その前に表記を簡潔にするため、数列を
で定義します(ついでに、想定されている規則に[たぶん]反せずに含められる 11 も 101 の前に入っています)。
素因数分解の出力では、後のプログラムの出力で( 7 が先に見つかるので) 隠れていた 11 も出ています。
:
奇数番項(2k + 1, k = 0, 1, 2, ...)はすべて、11 を素因数として含んでいます。
計算機まかせではなく筆算でもしてみると帰納的にわかります。
→奇数番項はすべて合成数であり、素数が含まれる可能性が残るのは、偶数番項で構成される部分数列内に絞られて「大きさ」は半分に。
(追記:最初の 11, 101 は素数ですけど、ここでは他の素数を探すと言う意味で)
同様にして
:
(4k + 2, k = 0, 1, 2, ...)番項はすべて、101 を素因数として含んでいます。
計算機まかせではなく筆算でもしてみると帰納的にわかります。
→(4k + 2, k = 0, 1, 2, ...)番項はすべて合成数です。
{4k + 2| k = 0, 1, 2, ...}は、4 で割ると 2 余る自然数の集合です。前のステップで、素数候補は偶数番項に絞られましたが、このステップで 4 で割ると 2 余る数(当然、偶数)もアウトのため、素数が含まれる可能性が残るのは、第(4 の倍数)項だけになりました。
同様にして
:
(8k + 4, k = 0, 1, 2, ...)番項はすべて、73 を素因数として含んでいます。
計算機まかせではなく筆算でもしてみると帰納的にわかります。
→(8k + 4, k = 0, 1, 2, ...)番項はすべて合成数です。
{8k + 4| k = 0, 1, 2, ...}は、8 で割ると 4 余る自然数の集合です。前のステップで、素数候補は(4の倍数)番項に絞られましたが、このステップで 8 で割ると 4 余る数(当然、4 の倍数)もアウトのため、素数が含まれる可能性が残るのは、ここまでで第(8 の倍数)項だけということになりました……
ところで、YMNさんが見つけだした「凶悪」な数(最小の素因数が、1265011073である数)は、ここでの定義でいうと(元発言とでは 1 ずれるので)第64項です。 これは第(16 の倍数)項の 1 つです。
#6/3 追記で補足
投票数:0
平均点:0.00
返信する
YMN
投稿数: 1018

>、素数が含まれる可能性が残るのは、ここまでで第(8 の倍数)項だけということになりました……
>ところで、YMNさんが見つけだした「凶悪」な数(最小の素因数が、1265011073である数)は、ここでの定義でいうと(元発言とでは 1 ずれるので)第64項です。 これは第(16 の倍数)項の 1 つです。
「10...01の系列で、全てかどうかは分からないけれど少なくとも(100*7/8=)87.5%以上、すなわち殆どは素数ではない」ということの説明になりますね。
>>素数でないものが続きましたが、1025桁(つまり間の0が23個)で長大な時間がかかりメモリが足らなくなったのかハングアップしてしまいました。
()内の23個は間違いで1023個でした。
突破不可能な最初にぶち当たった本当に「凶悪」なのはこやつで、1024というどこかで見かけた数が浮かび上がってくるのでした。
>ところで、YMNさんが見つけだした「凶悪」な数(最小の素因数が、1265011073である数)は、ここでの定義でいうと(元発言とでは 1 ずれるので)第64項です。 これは第(16 の倍数)項の 1 つです。
「10...01の系列で、全てかどうかは分からないけれど少なくとも(100*7/8=)87.5%以上、すなわち殆どは素数ではない」ということの説明になりますね。
>>素数でないものが続きましたが、1025桁(つまり間の0が23個)で長大な時間がかかりメモリが足らなくなったのかハングアップしてしまいました。
()内の23個は間違いで1023個でした。
突破不可能な最初にぶち当たった本当に「凶悪」なのはこやつで、1024というどこかで見かけた数が浮かび上がってくるのでした。
投票数:0
平均点:0.00
返信する
FarSeer08
投稿数: 278

ところで、少々懐かしかったものの、今さら BASIC で書くのは(個人的感想ですが)やはり面倒なので、他で使える多桁計算のライブラリを探してみました。当然のごとく出てくる GNU 以外に、なんと、かつてニフティサーブ(の一部)をその深い発言で席巻した「妖精」さんが、JavaScript用のシンプルなライブラリを公開されているのでした(TinyBigInt)。
となれば、素因数分解でテケトーな速度比較をGO。素因数分解のアルゴリズムは基本的に以前の発言で出ているシンプルな形のままで、何も効率化はしていません(十進BASIC版は、ほとんどわからない程度に効率化の逆にはなりますが、GOTO、GOSUBから、VisualBASICなどと同等の外部サブプログラムの形にしました。他のプログラムと見比べやすいはずです)
十進BASIC(1000桁十進モード) 38.2 sec.
十進BASIC(有理数モード) 38.53 sec.
TinyBigInt 2.583 sec.
GNU MP 0.070289 sec.
コンパイラを使い世界最速を目指す(謎) GNU MPが速いのは当然ですが、21世紀のBASICと呼ばれる(噓)JavaScriptで手軽にこの速度が利用できるのはいいかもしれません。
※TinyBigInt版は一部本来の性能を活かしていない箇所があるので(謎)、もうほんの少し速くなるかも。
※GNU MP版は最初に目についた整数ライブラリを使っていますが、自然数専用ライブラリを使うと、もうほんのほんの少し速くなるかも。
が、そもそもなんやかんや動かしているマシン上でやってるテケトーなテストなので気にすることはないでしょう。
十進BASIC版(有理数モード)
TinyBigInt版(JavaScript)
GNU MP版(C)
となれば、素因数分解でテケトーな速度比較をGO。素因数分解のアルゴリズムは基本的に以前の発言で出ているシンプルな形のままで、何も効率化はしていません(十進BASIC版は、ほとんどわからない程度に効率化の逆にはなりますが、GOTO、GOSUBから、VisualBASICなどと同等の外部サブプログラムの形にしました。他のプログラムと見比べやすいはずです)
十進BASIC(1000桁十進モード) 38.2 sec.
十進BASIC(有理数モード) 38.53 sec.
TinyBigInt 2.583 sec.
GNU MP 0.070289 sec.
コンパイラを使い世界最速を目指す(謎) GNU MPが速いのは当然ですが、21世紀のBASICと呼ばれる(噓)JavaScriptで手軽にこの速度が利用できるのはいいかもしれません。
※TinyBigInt版は一部本来の性能を活かしていない箇所があるので(謎)、もうほんの少し速くなるかも。
※GNU MP版は最初に目についた整数ライブラリを使っていますが、自然数専用ライブラリを使うと、もうほんのほんの少し速くなるかも。
が、そもそもなんやかんや動かしているマシン上でやってるテケトーなテストなので気にすることはないでしょう。
十進BASIC版(有理数モード)
OPTION ARITHMETIC RATIONAL
LET n_term = 18
DIM n(20)
FOR i = 1 TO 20
LET n(i) = 10^i +1
NEXT I
LET ts = TIME
FOR i = 1 TO n_term
PRINT i; ")"; n(i); " = ";
CALL factorize(n(i))
PRINT
NEXT I
LET te = TIME
PRINT "Elapsed time: "; te - ts; "sec"
END
EXTERNAL SUB factorize(n)
OPTION ARITHMETIC RATIONAL
LET f = 0
DO
CALL factor(f, n)
PRINT f;
IF n = 1 THEN
EXIT DO
END IF
LOOP
END SUB
EXTERNAL SUB factor(f, n)
OPTION ARITHMETIC RATIONAL
LET m=SQR(n)
FOR f=2 TO m
IF MOD(n, f) =0 THEN
LET n = n/f
EXIT SUB
END IF
NEXT f
LET f = n
LET n = 1
END SUB
TinyBigInt版(JavaScript)
var TBI1 = new TinyBigInt(1);
var TBI2 = new TinyBigInt(2);
var N_TERM = 18;
var a = new Array();
for (var i = 0; i < N_TERM; i++){
for (var j = 0, z = ""; j < i; j++){
z = z + "0";
}
a[i] = new TinyBigInt("1" + z + "1");
}
var ts = Date.now();
var i = 0;
for (var ae of a){
i++;
var msg = i +") "+ ae +" = ";
factorize(ae);
print(msg);
}
var te = Date.now();
print("Ealpsed time: "+(te - ts)/1000 +" sec.");
function factorize(ae){
do {
var r = factor(ae);
msg = msg +" "+ r.f;
ae = r.n;
} while( r.n.compare(TBI1));
}
function factor(n){// n: TynyBigInt
var m = n.sqrt();
var i = TBI2;
while(i.compare(m) <= 0){
if (!n.mod(i).compare(0)){
return {f: i, n: n.div(i)};
}
i = i.add(1);
}
return {f: n, n: TBI1};
}
GNU MP版(C)
#include <stdio.h>
#include <sys/time.h>
#include <gmp.h>
#define N_TERM 18
extern void factorize(mpz_t n);
extern void factor(mpz_t f, mpz_t n);
mpz_t C0, C1, C2;
int main()
{
unsigned long a = 1001;
mpz_t mp[N_TERM];
char mp_s[1000];
struct timeval ts, te;
mpz_init_set_str(C0, "0", 10);
mpz_init_set_str(C1, "1", 10);
mpz_init_set_str(C2, "2", 10);
mp_s[0] = '1';
for (int i = 0; i < N_TERM; ++i){
for (int j = 1; j < i+1; ++j){ mp_s[j] = '0';}
mp_s[i+1] = '1';
mp_s[i+2] = '\0';
mpz_init_set_str(mp[i], mp_s, 10);
}
gettimeofday(&ts, NULL);
for (int i = 0; i < N_TERM; ++i){
printf("%03d) ", i+1);
mpz_out_str(NULL, 10, mp[i]);
printf(" = ");
factorize(mp[i]);
printf("\n");
}
gettimeofday(&te, NULL);
printf("Elapsed time: %f sec.\n", (te.tv_sec - ts.tv_sec) + (te.tv_usec - ts.tv_usec)/1000000.0);
}
void factorize(mpz_t n)
{
mpz_t f;
mpz_init(f);
do {
factor(f, n);
mpz_out_str(NULL, 10, f);
printf(" ");
} while (mpz_cmp(n, C1));
}
void factor(mpz_t f, mpz_t n)
{
mpz_t ub, q, r;
mpz_t i, ii;
mpz_init(q);
mpz_init(r);
mpz_init(ub);
mpz_init(ii);
mpz_sqrt(ub, n);
mpz_set(i, C2);
while (mpz_cmp(i, ub) <= 0){
mpz_fdiv_qr(q, r, n, i);
if (!mpz_cmp(r, C0)){
mpz_set(f, i);
mpz_set(n, q);
return;
}
mpz_add(ii, i , C1);
mpz_set(i, ii);
}
mpz_set(f, n);
mpz_set(n, C1);
}
投票数:2
平均点:5.00
返信する
Chryso
投稿数: 6387

現代暗号入門(ブルーバックス)
これは良書だった。
無線LANのWFP、WPA、マイナンバー、非接触ICカード、ビットコイン、これらの個人認証について、具体的な説明がありました。
RSAの場合、素数同士の掛け算で公開鍵を作り、 個人認証を成立させている。素数の因数分解には、「まだ」効率的な方法が見つかっていません。そのため、因数分解はわかっている素数で小さいほうから総当たり戦で割っていく方法。このためコンピューターのリソースがかなり使われている様子。
最初からなにとなにをかけたら、その数字(公開鍵)になるのか、「知っていれば」2つの数字(1つは秘密鍵)を知るのはすぐですが、知らないと計算に相当時間がかかることを応用。
もっとも素数はそのうちに足りなくなるようです。また、コンピューターの計算能力は今のところは、追いつかないだろうと言われていますが、そのうちに計算能力が上がって、追いついてしまうということが指摘されています。
その時はその時で、素数にたよらない関数で公開鍵を作るというわけで、意外と泥臭い話だと思ってしまいました。
これは良書だった。
無線LANのWFP、WPA、マイナンバー、非接触ICカード、ビットコイン、これらの個人認証について、具体的な説明がありました。
RSAの場合、素数同士の掛け算で公開鍵を作り、 個人認証を成立させている。素数の因数分解には、「まだ」効率的な方法が見つかっていません。そのため、因数分解はわかっている素数で小さいほうから総当たり戦で割っていく方法。このためコンピューターのリソースがかなり使われている様子。
最初からなにとなにをかけたら、その数字(公開鍵)になるのか、「知っていれば」2つの数字(1つは秘密鍵)を知るのはすぐですが、知らないと計算に相当時間がかかることを応用。
もっとも素数はそのうちに足りなくなるようです。また、コンピューターの計算能力は今のところは、追いつかないだろうと言われていますが、そのうちに計算能力が上がって、追いついてしまうということが指摘されています。
その時はその時で、素数にたよらない関数で公開鍵を作るというわけで、意外と泥臭い話だと思ってしまいました。
投票数:0
平均点:0.00
返信する
YMN
投稿数: 1018

宇宙人とコンタクトしていると称して、宇宙人からのメッセージを述べる人がいます。
その内容は大抵は愛だの平和だのといった類で、宇宙人でなくても誰でも思いつきそうなことです。
現在人類が知りえている最大の素数より大きい素数を示せば、話の信ぴょう性はかなり高まることになります。
その提示された数が本当に素数かどうかの検証が人類にできなければ無意味ですが、未知の素数の発見に比べれば、提示された数が素数かどうかの検証はピンポイントのサーチになり、極端に大きくない限りは可能かと思います。
その内容は大抵は愛だの平和だのといった類で、宇宙人でなくても誰でも思いつきそうなことです。
現在人類が知りえている最大の素数より大きい素数を示せば、話の信ぴょう性はかなり高まることになります。
その提示された数が本当に素数かどうかの検証が人類にできなければ無意味ですが、未知の素数の発見に比べれば、提示された数が素数かどうかの検証はピンポイントのサーチになり、極端に大きくない限りは可能かと思います。
投票数:0
平均点:0.00
返信する
YMN
投稿数: 1018

https://wired.jp/2016/01/22/discover-your-own-prime-number/
----引用
これまでで最大となる2,233万8,618桁の素数(49番目のメルセンヌ素数)が、昨年9月に発見されていたことが判明した。過去最大だった48番目よりも500万桁大きいものだ。
----引用終了
現在知りえている最大の素数がどのくらいなのか調べてみました(これが最新かどうかは分かりませんけど)。
(休日無し)1日8時間労働で1秒にひとつの数値を言うとして(実際はもっと速く言えそうですが)、どのくらいかかるかというと
22338618/(60*60*8)=776日
ということで、大変ではあるけれど口頭で伝えることが不可能というほどでもないことになります。
----引用
これまでで最大となる2,233万8,618桁の素数(49番目のメルセンヌ素数)が、昨年9月に発見されていたことが判明した。過去最大だった48番目よりも500万桁大きいものだ。
----引用終了
現在知りえている最大の素数がどのくらいなのか調べてみました(これが最新かどうかは分かりませんけど)。
(休日無し)1日8時間労働で1秒にひとつの数値を言うとして(実際はもっと速く言えそうですが)、どのくらいかかるかというと
22338618/(60*60*8)=776日
ということで、大変ではあるけれど口頭で伝えることが不可能というほどでもないことになります。
投票数:0
平均点:0.00
返信する