剰余をコンピュータで効率よく算出する方法

剰余をコンピュータで効率よく算出する方法を教えていただきたいです。
x-int(x/y)*yと同様にすれば比較的簡単に求められることは知っているのですが、計算対象が64266330917908644872330635228106713310880186591609208114244758680898150367880703152525200743234420230進数で整数部だけで最大268435456桁というデータ型の為、不用意に割り算や掛け算をしたくないというところがあります。
何か良い方法はないでしょうか。

参考としてJavaにあるBigDecimalの有効桁数が約64643000桁程度に対して計算対象は10進数に変換すると約3000000000桁程度になるので50倍弱の精度のデータを計算してしまう危険があります。

No.4 ベストアンサー 回答者： kmee 回答日時： 2015/08/26 05:10

基数B=642... とします。

例えば、このB進法で 1/8 を小数表記することを考えてください。
1/8 = 1/(2^3)
= (3〜251の素数を掛けた合成数 ^3)/ ((2^3)*(3〜251の素数を掛けた合成数 ^3))
= (3〜251の素数を掛けた合成数 ^3) * (B^-3 )
です。つまり、1/8みたいな簡単なものでも、このB進数では小数3桁必要です。
1/8程度の有理数が小数1桁では表現できません。

小数1桁(0.1≦x<1)になる可能性のある 既約分数 m/n (1≦m≦n≦B) で、
・ n が 2〜251のいずれかの素数の2乗を約数に持つ→ 誤差なく表現するには小数2桁以上必要
・ n が 251を越える素因数を持つ→ 有限の桁では表現できない
です。
基数に10進101桁も使っているのに、誤差無く小数1桁にできる nはたった2^53=9007199254740992 (9.0*10^15)通りしかありません。
「(十分な精度の整数を使った)有理数型」なら、この範囲の全てで誤差はありません。
　ほとんどの場合、nに100桁も使う必要も無いでしょう。


また、(3〜251の素数を掛けた合成数 ^3) * (B^-3 ) を小数表記するには
小数第1位: (3〜251の素数を掛けた合成数 ^3) / B^2 の商
小数第2位: (↑の余り) / B の商
小数第3位: ↑の余り
となり、計算量が増えます。


無理数で誤差が出るのは、どんな基数を使っても避けられません。
これを、例えば π ≒ P/B とでも近似しようということなのかもしれませんが、
そんな複雑な基数を使わなくても Pd/10^102 や Pb/2^335 の方が誤差が少なくなります。
多くの種類の素数の合成数なので、約分できる可能性が大きい→効率がよくなる、という効果を狙っているかもしれませんが、上で述べたような事情から、そうなる可能性は極めて低いと言えるでしょう。



以上のようなことから、 B進小数にこだわらない方が、精度も速度もメモリも効率がよくなります。
やり方を考えなおした方がよいでしょう。

No.3 回答者： kmee 回答日時： 2015/08/25 00:21

>数十GBクラスのメモリでは、求める精度から考慮すると日常生活の範囲で言えば「円周率は3かもしれないし4かもしれない」と言っているようなレベルに近いです。

が本当なら、通常のPCでは無理です。

ただ、
> 10進数に変換すると約3000000000桁程度
なら、100MBちょっとです。



Javaにこだわるのでなければ、例にあげた Ruby や Python では「メモリのゆるす限りのビット数」の整数が扱えます。
GMPも有名です。
https://ja.wikipedia.org/wiki/GNU_Multi-Precisio …

剰余は、場合によっては合同式の性質を使って、下処理することで、小さな計算に分割できるかもしれません。
https://ja.wikipedia.org/wiki/%E6%95%B4%E6%95%B0 …




> 10進数では1/3という小さな割り算で循環小数化してしまう

もしかして、本当の目的は「有理数を誤差無く計算したい」ということではないですか?
それなら。「どんな値が来ても高々『数桁』の有限小数にできる基数を使った小数表現」を使うのではなく、
「既約分数 a / b のaとbを保持するようなクラス」と、計算用メソッドを用意すれば、無駄な桁や利用しない素数を省けて、計算量も減るのでは?

PythonやRubyには、有理数をそのまま扱うクラスがあります。

この回答へのお礼

＞PythonやRubyには、有理数をそのまま扱うクラスがあります。
その有理数をそのまま扱うというのはロジック的に割り算を最後まで遅延させる設計にすれば良いだけの問題なので必要としていません。

必要としているのは√、π、ラジアンに対する三角関数等無理数の侵入が避けられない演算へと入る直前に、有理数側で対策を打って打切り誤差を発生させずに割り算を成功させて置く事です。
Cobolにて10進数での演算を行うと1/4近いデータに計算の途中で避けられる誤差が入り込む状況なので、
とりあえず253までの素数の合成数による割り算まで許容しておけば例外的なデータに絞り込めると考えているわけです。
今はGPGPUで処理しやすいように2乗しても32ビットに収まる範囲の基数に納めていますが、
正しく計算しきれない分については更に大きな基数での計算をする事になるので今のうちから軽い設計にできる場所はそうしておきたいというものです。

お礼日時：2015/08/25 23:24

No.2 回答者： kmee 回答日時： 2015/08/23 21:41

ただ余りを計算するだけなら、大抵の言語、ライブラリ等に「整数同士の割り算の余りを計算する」方法が用意されています。

Javaが出てきたので例に使うと
https://docs.oracle.com/javase/jp/6/api/java/mat …
でBigDecimalの余りを求められます。

また、商と余りを同時に返すものもあります
https://docs.oracle.com/javase/jp/6/api/java/mat …

割り算部分を自作するのなら、小学校でやった筆算と同じことです。
上の桁から引けるかどうか調べていったものが「商」で、割り切れずに残ったものが「余り」です。

remainderはx-int(x/y)*yだと書いてあります。
divideAndRemainderは
> 整数の商と剰余の両方が必要な場合、divideToIntegralValue メソッドと remainder メソッドを別々に使用するより、除算を 1 回だけ実行すればよいこのメソッドの方が高速であることに留意してください。
とあることから上記の「商も計算して残ったものが『余り』」という手法のようです。


JavaのBigDecimalは制限があるようですが、 Rubyの整数、Pythonの長整数等は「メモリがある限り無限」としています。
どうちも、余りは % 演算子で計算できます。
またdivideAndRemainder と同様の
http://docs.ruby-lang.org/ja/2.1.0/method/Numeri …
http://docs.python.jp/2/library/functions.html#d …
もあります。

この回答へのお礼

>ただ余りを計算するだけなら、大抵の言語、ライブラリ等に「整数同士の割り算の余りを計算する」方法が用意されています。
それが利用可能なのであればどんなに良い事だろうかと思いますが251までの全ての素数を含む特殊な進数を使用しているのは尋常ではないレベルの高精度演算を求めています。
10進数では1/3という小さな割り算で循環小数化してしまうので数十GBクラスのメモリでは、求める精度から考慮すると日常生活の範囲で言えば「円周率は3かもしれないし4かもしれない」と言っているようなレベルに近いです。
そのような精度の計算の中でも余りが必要な場面がある為、このような特殊な事態になっています。
今の基数や桁数はこの範囲でオーバーフローしないでくれればうれしいなという希望です。
この基数で足りなければオーバーフローした演算から更に大きな基数でやり直すつもりです。

＞するより、除算を 1 回だけ実行すればよいこのメソッドの方が高速であることに留意してください。
＞とあることから上記の「商も計算して残ったものが『余り』」という手法のようです。
やはり全桁走査するしかない物なのでしょうか。
いったんはOpenJDKのBigDecimalを参考に実装しながら更に良い方法がないか探してみます。

お礼日時：2015/08/24 22:31

No.1 回答者： 銀鱗 回答日時： 2015/08/23 20:53

桁を分けて計算すれば良い。

1234×5=(1200+34)×5=(12×5)×100＋(34×5)
こんな感じ。

この回答へのお礼

申し訳ありません。必要としているのは掛け算ではなく割り算の余りの出し方です。

お礼日時：2015/08/24 21:44