ある数を上位と下位の2変数にわけて格納し、二乗を計算するアルゴリズム

Question

ある数の二乗を計算したいのですが、オーバーフローを起こさないために上位と下位で分けようと思っています。
分割後、これらを使って二乗した値をまた2つの変数に上位と下位にわけて格納しようと思っています。
例えば123456789ならupper=1234567、lower=89のような感じで、適当に分割して、upperとlowerをうまく使って2乗を計算したいのですが、どうすれば実現できるでしょうか？

Answer 1

おそらく求めてるのはこれでしょう
例としてNを32bit整数、hibit(x)を32bit整数xの上位16bit、lobit(x)を下位16bitだとしたとき、

N = hibit(N) << 16 + lobit(N)

が成り立ちます。
なので

N^2 = hibit(N)^2 << 32 + 2 * hibit(N) * lobit(N) << 16 + lobit(N)^2

計算結果は64bitで表せるので、上位32bitをleft、下位32bitをrightに入れるとすると

right = lobit(2 * hibit(N) * lobit(N)) << 16 + lobit(N)^2 - [オーバーフロー分]
left = hibit(N)^2 + 2 * hibit(N) * lobit(N) >> 16 + [rightがオーバーフローしてたら1]

こんな感じで計算できます。(hibit(x)もlobit(x)も16bitで表せる数なので、それらの積は32bitに収まります)
ただし実装するにあたっては、2 * hibit(N) * lobit(N)が32bitを超えた場合にどうなるかとかどうやってrightのオーバーフローを検知するかで難易度も変わってくるので、Nが32bitフルに使わなくても表せるような数だった場合には余裕のある分割の仕方に変えることも検討してください。

Answer 2

ネットで調べた方が早くありませんか？

多倍長整数の演算

Answer 3

(100a+b)^2 = 10000aa + 200ab + bb (a=1234567, b=89) でいぃんじゃね?

Answer 4

１００で割る、１００の余りを出す、でできますね