Pascalの三角形 #9

60段目までPascalの三角形の値を計算すると、
そこに現れる最大値は60段目の中央の値=118264581564861424である。
実際にpascal3.gが生成したグラフ中でname属性が"60_30"のノードのlabel属性は、

$ gvpr -fpascal3.g -a60 | gvpr "N [name == '60_30'] { print(label); }"
118264581564861424

であり一致する。
64ビット符号あり整数の最大値は9223372036854775807なので60段目までの計算ではこれをオーバーしないが、
70段目なら=112186277816662845432であり、もはや64ビット整数の範囲を遥かに超える。
実際、計算された"70_35"のノードのlabel属性は、

$ gvpr -fpascal3.g -a70 | gvpr "N [name == '70_35'] { print(label); }"
1505813374405535736

であり、オーバーフローを起こして正しい値になっていないことが分かる。

段数が増えていくとPascalの三角形としては正しくなくなる。
ところが、この誤った値を含むPascalの三角形をsierpinski2.gでフィルタして作成したSierpinskiの三角形は、

$ gvpr -fpascal3.g -a100 | gvpr -c -fsierpinski2.g | dot -Tpng -osierpinski_100.png

となり、確実に誤った値に基づく100段目までのものでも正しく出力されている。
これは、このSierpinskiの三角形ではPascalの三角形の値の2を法とする剰余でノードの白黒を決定するからである。
下位の段の二つの値を加算した時に9223372036854775807=2⁶³-1を超えてオーバーフローしても、
2を法とする剰余系で考えれば求められた値は正しい結果となる。
つまり、偶数同士、奇数同士の加算はオーバーフローしても結果は偶数であり、
偶数と奇数との加算の結果はオーバーフローしても奇数になるということである。