Python で階乗関数を次のように定義します。
def fact(n):
if n == 1:
return n
else:
return n * fact(n-1)
print(fact(100))
Juliaでは次のようになります。
function fact(n)
if n == 1
n
else
n * fact(n-1)
end
end
println(fact(100))
Python プログラムは、100 の評価に対して非常に大きな数を返します (予想どおり)。Julia は 0 を返します。小さい数 (10 など) では、どちらも機能します。
2 つの質問があります。
Julia には、個別の固定サイズの整数型と BigInt 型があります。デフォルトのタイプはInt64で、もちろん 64 ビットです。
100以来！約526ビットかかり、明らかにオーバーフローしInt64ます.
この問題は、実行するだけで解決できfact(BigInt(100))ます (実行したと仮定しrequireて)。もちろん、fact関数内で変換を実行することもできます。
昔々、Pythonは同じでした。intマシンに応じて16ビット、32ビット、または64ビットの別々のタイプとlong、任意の長さの がありました。プログラムを Python 1.5 で実行すると、Julia のようにラップ アラウンドするか、例外が発生します。解決策は、 を呼び出すか、関数内でfact(100L)変換を行うことです。longfact
ただし、2.x シリーズのある時点で、Python は 2 つの型を結び付けたためint、オーバーフローしたものは自動的にlong. そして、3.0 で 2 つのタイプが完全に統合されたため、分離はなくlongなりました。
では、Julia がエラーを発生させずに単にオーバーフローするのはなぜでしょうか?
FAQ では、 Julia がネイティブ マシンの整数演算を使用する理由を実際に説明しています。これには、オーバーフロー時のラップアラウンド動作が含まれます。
「ネイティブ マシン演算」とは、一般に「ほぼすべての 2 の補数マシンで C が行うこと」を意味します。特に Julia や Python などの言語は、もともと C の上に構築されていて、金属にかなり近いものでした。Julia の場合、これは単なる「デフォルト」ではなく、意図的な選択です。
C では (少なくとも当時は)、実際には、次のような符号付き整数型をオーバーフローさせた場合にどうなるかは実装次第ですが、int642 の補数演算をネイティブに使用するほとんどすべてのプラットフォーム (これは、ほとんどすべてのプラットフォームです)今日を参照してください)、まったく同じことが起こります: 上位 64 ビットより上のすべてを切り捨てるだけです。つまり、正から負にラップアラウンドします。実際、 C でこのように動作するには、符号なし整数型が必要です(一方、C は、ほとんどの CPU がこのように動作するため、このように動作します)。
C では (ほとんどの CPU の機械語とは異なり)、事後にオーバーフローが発生したことを検出する方法がありません。したがって、 を発生させたい場合はOverflowError、乗算を実行する前に、乗算がオーバーフローすることを検出するロジックを作成する必要があります。そして、すべての乗算でそのロジックを実行する必要があります。インライン アセンブリ コードを記述することで、一部のプラットフォーム用にこれを最適化できる場合があります。int64または、より大きな型にキャストすることもできますが、(a) コードが遅くなる傾向があり、(b) 最大の型 (今日の多くのプラットフォームで使用されている)を既に使用している場合は機能しません。
Python では、各乗算を最大 4 倍遅くすること (通常はそれより遅くなりますが、それほど大きくなる可能性があります) は大したことではありません。なぜなら、Python は乗算よりもバイトコードのフェッチと整数オブジェクトのボックス化解除に多くの時間を費やすからです。しかし、Julia はそれよりも高速であることを意図しています。
ジョン・マイルズ・ホワイトがComputers are Machinesで説明しているように:
多くの点で、Julia は、C から Python のような言語への移行で失われた力の一部を回復しようとする試みによって、他の新しい言語と一線を画しています。しかし、移行にはかなりの学習曲線が伴います。
しかし、これには別の理由があります。オーバーフローする符号付き算術演算は、多くの場合に実際に役立ちます。符号なし算術演算のオーバーフローほど多くはありません(これが、C が最初の ANSI 仕様の前から符号なし算術演算をそのように動作するように定義している理由です) が、ユースケースはあります。
また、ロールオーバーよりも頻繁に型変換が必要になる場合でも、ロールオーバーよりも手動で型変換を行う方がはるかに簡単です。Python でこれを行ったことがある場合、オペランドを選択し%て符号を正しく取得することは、確かに間違いやすいものです。へのキャストは、台無しにするのBigIntがかなり難しいです。
そして最後に、Python と Julia の両方のように、強く型付けされた言語では、型の安定性が重要です。Python 3 が存在する理由の 1 つは、古いstr型が魔法のように変換されてunicode問題が発生したことです。int型が魔法のように変換されて問題が発生することはあまり一般的でlongはありませんが、発生する可能性があります (たとえば、ネットワークから、または C API を介して値を取得し、結果を同じ形式で書き出すことを期待している場合)。 . Python の開発チームは、int/long統合を行う際にこれについて議論し、「実用性は純粋性よりも優れている」などの禅のさまざまな部分を引用し、最終的には古い動作が新しい動作よりも多くの問題を引き起こしたと判断しました。ジュリアのデザインは反対の決定を下しました。
Julia の結果が 0 である理由を誰も答えません。
Julia はオーバーフローの整数乗算をチェックしないため、64 ビット整数の乗算は mod 2^63 で実行されます。このよくある質問のエントリを参照してください
階乗の乗算を書き出すと、得られる
1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20*21*22*23*24*25*26*27*28*29*30*31*32*33*34*35*36*37*38*39*40*41*42*43*44*45*46*47*48*49*50*51*52*53*54*55*56*57*58*59*60*61*62*63*64*65*66*67*68*69*70*71*72*73*74*75*76*77*78*79*80*81*82*83*84*85*86*87*88*89*90*91*92*93*94*95*96*97*98*99*100
これは素因数とも書ける
2^97 * 3^48 * 5^24 * 7^16 * 11^9 * 13^7 * 17^5 * 19^5 * 23^4 * 29^3 * 31^3 * 37^2 * 41^2 * 43^2 * 47^2 * 53^1 * 59^1 * 61^1 * 67^1 * 71^1 * 73^1 * 79^1 * 83^1 * 89^1 * 97^1
の指数を見ると、2が得られ97ます。モジュラー演算では、計算のどのステップでも mod 関数を実行でき、結果には影響しません。2^97 mod 2^63 == 0チェーンの残りの部分と乗算した値も 0 です。
更新: もちろん、私は紙の上でこの計算を行うのが面倒でした。
d = Dict{Int,Int}()
for i=1:100
for (k,v) in factor(i)
d[k] = get(d,k,0) + v
end
end
for k in sort(collect(keys(d)))
print("$k^$(d[k])*")
end
Julia の標準ライブラリには、非常に便利な factor() 関数があります。
Julia が高速である理由の 1 つは、パフォーマンスを低下させる機能を回避していることです。これはそれらの1つです。Python では、解釈されたものは、自動的に BigInt ライブラリに切り替える必要があるかどうかを常にチェックします。その絶え間ないチェックには代償が伴います。
これがあなたが望むことをする関数です：
function fact(n)
if n == 0
1
else
big(n) * fact(n-1)
end
end
println( fact(100) )
println( fact(0) )
私はあなたのプログラムのバグを自由に修正しました。
function !(n)
if n == 0
1
else
big(n) * !(n-1)
end
end
println( !(100) )
println( !(0) )
私は個人的にはこれをしません。関数は、従来、引数を変更する関数に使用されます。しかし、私はオプションを提供したかったのです。最後に、次の 1 行の代替案を提示せずにはいられません。
fact(n) = n == 0 ? 1 : big(n) * !(n-1)
println( fact(100) )
println( fact(0) )
ちなみに、ジュリアでこれを行う慣用的な方法は、型システムを利用して、異なる型の異なるバージョンをコンパイルすることだと思います。
fact(n) = n <= zero(n) ? one(n) : n*fact(n-one(n))
# one(n) gives you a one, as it were, of the same type as n
次に、その関数の別のバージョンがコンパイルされ、入力の型に応じて呼び出されます。ユーザーは、使用する型と、呼び出す関数のバージョンを決定する必要があります。
julia> fact(10)
3628800
julia> fact(100)
0
julia> fact(BigInt(100))
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
BigInt 対マシン (Int64) 演算のオーバーヘッドは、@abarnert によってよく説明されていますが、Int64 対 BigInt fact() の (LLVM) コンパイル バージョンを見るとわかります。
julia> code_llvm(fact,(Int64,))
define i64 @"julia_fact;23421"(i64) {
top:
%1 = icmp sgt i64 %0, 0, !dbg !10800
br i1 %1, label %L, label %if, !dbg !10800
if: ; preds = %top
ret i64 1, !dbg !10800
L: ; preds = %top
%2 = add i64 %0, -1, !dbg !10800
%3 = call i64 @"julia_fact;23398"(i64 %2), !dbg !10800
%4 = mul i64 %3, %0, !dbg !10800
ret i64 %4, !dbg !10800
}
julia> code_llvm(fact,(BigInt,))
define %jl_value_t* @"julia_fact;23422"(%jl_value_t*, %jl_value_t**, i32) {
top:
%3 = alloca [6 x %jl_value_t*], align 8
%.sub = getelementptr inbounds [6 x %jl_value_t*]* %3, i64 0, i64 0
%4 = getelementptr [6 x %jl_value_t*]* %3, i64 0, i64 2, !dbg !10803
store %jl_value_t* inttoptr (i64 8 to %jl_value_t*), %jl_value_t** %.sub, align 8
%5 = load %jl_value_t*** @jl_pgcstack, align 8, !dbg !10803
%6 = getelementptr [6 x %jl_value_t*]* %3, i64 0, i64 1, !dbg !10803
%.c = bitcast %jl_value_t** %5 to %jl_value_t*, !dbg !10803
store %jl_value_t* %.c, %jl_value_t** %6, align 8, !dbg !10803
store %jl_value_t** %.sub, %jl_value_t*** @jl_pgcstack, align 8, !dbg !10803
store %jl_value_t* null, %jl_value_t** %4, align 8, !dbg !10803
%7 = getelementptr [6 x %jl_value_t*]* %3, i64 0, i64 3
store %jl_value_t* null, %jl_value_t** %7, align 8
%8 = getelementptr [6 x %jl_value_t*]* %3, i64 0, i64 4
store %jl_value_t* null, %jl_value_t** %8, align 8
%9 = getelementptr [6 x %jl_value_t*]* %3, i64 0, i64 5
store %jl_value_t* null, %jl_value_t** %9, align 8
%10 = load %jl_value_t** %1, align 8, !dbg !10803
%11 = call %jl_value_t* @julia_BigInt2(i64 0), !dbg !10804
store %jl_value_t* %11, %jl_value_t** %4, align 8, !dbg !10804
%12 = getelementptr inbounds %jl_value_t* %10, i64 1, i32 0, !dbg !10804
%13 = getelementptr inbounds %jl_value_t* %11, i64 1, i32 0, !dbg !10804
%14 = call i32 inttoptr (i64 4535902144 to i32 (%jl_value_t**, %jl_value_t**)*)(%jl_value_t** %12, %jl_value_t** %13), !dbg !10804
%15 = icmp sgt i32 %14, 0, !dbg !10804
br i1 %15, label %L, label %if, !dbg !10804
if: ; preds = %top
%16 = call %jl_value_t* @julia_BigInt2(i64 1), !dbg !10804
%17 = load %jl_value_t** %6, align 8, !dbg !10804
%18 = getelementptr inbounds %jl_value_t* %17, i64 0, i32 0, !dbg !10804
store %jl_value_t** %18, %jl_value_t*** @jl_pgcstack, align 8, !dbg !10804
ret %jl_value_t* %16, !dbg !10804
L: ; preds = %top
store %jl_value_t* %10, %jl_value_t** %7, align 8, !dbg !10804
store %jl_value_t* %10, %jl_value_t** %8, align 8, !dbg !10804
%19 = call %jl_value_t* @julia_BigInt2(i64 1), !dbg !10804
store %jl_value_t* %19, %jl_value_t** %9, align 8, !dbg !10804
%20 = call %jl_value_t* @"julia_-;23402"(%jl_value_t* inttoptr (i64 140544121125120 to %jl_value_t*), %jl_value_t** %8, i32 2), !dbg !10804
store %jl_value_t* %20, %jl_value_t** %8, align 8, !dbg !10804
%21 = call %jl_value_t* @"julia_fact;23400"(%jl_value_t* inttoptr (i64 140544559367232 to %jl_value_t*), %jl_value_t** %8, i32 1), !dbg !10804
store %jl_value_t* %21, %jl_value_t** %8, align 8, !dbg !10804
%22 = call %jl_value_t* @"julia_*;23401"(%jl_value_t* inttoptr (i64 140544121124768 to %jl_value_t*), %jl_value_t** %7, i32 2), !dbg !10804
%23 = load %jl_value_t** %6, align 8, !dbg !10804
%24 = getelementptr inbounds %jl_value_t* %23, i64 0, i32 0, !dbg !10804
store %jl_value_t** %24, %jl_value_t*** @jl_pgcstack, align 8, !dbg !10804
ret %jl_value_t* %22, !dbg !10804
}