問題タブ [integer-division]

整数を除算しようとしていますが、結果として0になります。私は自分が間違っていることを理解していません。この例ではintのみを使用していますが、floatまたはdoubleを使用して同じ結果をテストしています。

私が使用するコードは次のとおりです。

私が得る結果は次のとおりです。

2011-01-09 16：45：53.411 XX [8296：207] askQuestions：5
2011-01-09 16：45：53.412 XX [8296：207] playerResult：2
2011-01-09 16：45：53.412 XX [ 8296：207]間違った答え：3
2011-01-09 16：45：53.413 XX [8296：207]パーセント正しい：0％
2011-01-09 16：45：53.414 XX [8296：207]パーセント間違った：0％
2011-01 -09 16：45：53.414 XX [8296：207]計算：5
2011-01-09 16：45：53.415 XX [8296：207]間違った答え：0％

助けていただければ幸いです:-)

私はこのコードを書いていました：

結果は 0 です。これはなぜですか?また、この問題を解決するにはどうすればよいですか?

このMIDP Java関数がどのように機能するかを誰かに説明してもらえますか? 使用されている演算子について特に興味があります。

どうもありがとう

私はコンピュータ サイエンスを専攻しており、アセンブリ言語が整数除算関数を処理する方法に興味があります。除算と mod の両方を与えながら、単純に分子に加算するのは非現実的であるように思われるので、ビット シフト、減算、および 2 つのルックアップ テーブルを使用して除算する別の方法を考え出しました。

基本的に、関数は分母を取り、2 の最大乗数に基づいて「ブロック」を作成します。したがって、15 で割ると 4 のバイナリ ブロックが作成され、5 で割ると 3 のバイナリ ブロックが作成されます。次に、最初の 2^block- を生成します。サイズは分母の倍数。倍数ごとに、最初のブロックの値をキーにして、最初のブロックの後に値をルックアップ テーブルに書き込みます。

例: 2 進数の 5 の倍数 - ブロック サイズ 3 (8 進数)

したがって、実際の手順には、最初のブロックを取得し、最初のブロックを左にビットシフトし、ブロックがマップする値を減算することが含まれます。結果の数値が 0 になる場合は完全に割り切れ、値が負になる場合はそうではありません。

別の列挙ルックアップ テーブルを追加すると、値が入ったときにカウンターにマップされ、除算の結果を計算できます。

例: 再び 5 の倍数

あとは、すべてのブロックをカウンター テーブルにマッピングするだけで、答えが得られます。
この方法にはいくつかの問題があります。

1. 答えが完全に割り切れない場合、関数はジャンクを返します。
2. 整数値が大きい場合、これは機能しません。これは、32 ビットまたは 64 ビット整数の最後で 5 ブロック サイズが切り捨てられるためです。
3. C の標準除算よりも約 100 倍遅いです。
4. 分母が除数の因数である場合、ブロックは複数の値にマップする必要があり、さらに多くのテーブルが必要になります。これは素因数分解で解決できますが、簡単/迅速な素因数分解について私が読んだすべての方法には、除算が含まれており、この目的を無効にしています。

質問が 2 つあります。まず、これに似たアルゴリズムは既に存在しますか? 辺りを見回しましたが、似たようなものは見当たらないようです。第二に、実際のアセンブリ言語は整数除算をどのように処理しますか?

スタック オーバーフローに投稿するのはこれが初めてです。

これが常に値 0.0 を返すのはなぜですか? また、これを 00.00 形式にフォーマットして文字列に変換したいですか?

n 個のサーバーからファイルを読み込んでおり、それぞれにファイルの 1/n をダウンロードさせたいと考えています。簡単な整数計算がうまくいくと思っていましたが、常にうまくいくとは限りません。

9 つのスレッドで分割された 26 バイトのファイルのように、適切な数の場合 (ばかげていることはわかっていますが、たとえば)、私の好みではうまくいきません。もっと良い方法があるはずです。何か案は？

私はFixedpointクラスを書いていますが、ちょっとした問題にぶつかりました...乗算、除算の部分、エミュレートする方法がわかりません。私は除算のオペレーターに非常に大まかな刺し傷を負いましたが、それは間違いだと確信しています。これまでのところ、次のようになります。

私は...あまり良いプログラマーではありません、ハハ！

クラスの「部分」は16ビット幅です（ただし、修正される前にオーバーフローの可能性があるための余地が必要だと思うので、長い32ビットとして表されます）。整数部分である「値」についても同じことが言えます。'part'がその操作の1つで0xFFFFを超えると、上位16ビットが' value'に追加され、次に、下位16ビットのみが残るようにパーツがマスクされます。これは、初期化リストで行われます。

質問するのは嫌ですが、このようなドキュメントをどこで見つけることができるか、あるいは「トリック」やこれら2つの演算子の実行方法を誰かが知っているなら、私はそれをとても嬉しく思います！私は数学に関してはばかです、そして誰かが以前にこれをしなければならなかったことを知っています、しかしグーグルを検索することは私を約束の地に一度も連れて行かなかった...

私は、大きな数を除算するアルゴリズムについて考えていました。剰余でbigintCをbigintDで除算します。ここで、基数bでのCの表現がわかっており、Dの形式はb^k-1です。例で示すのがおそらく最も簡単です。C=21979182173をD=999で割ってみましょう。

• 数字を3桁のセットとして書き込みます：21 979 182 173
• 左から順に、連続するセットの合計（999を法とする）を取ります：21 001 183 356
• 「999を超えた」セットの前にあるセットに1を追加します：22 001 183 356

実際、21979182173/999=22001183および残りは356です。

複雑さを計算しました。間違いがなければ、アルゴリズムはO（n）で機能するはずです。ここで、nは基数b表現のCの桁数です。また、C ++で非常に大雑把で最適化されていないバージョンのアルゴリズム（b = 10のみ）を実行し、GMPの一般的な整数除算アルゴリズムに対してテストしましたが、実際にはGMPよりもうまくいくようです。私が見たところ、このような実装されたものはどこにも見つからなかったので、一般的な部門に対してテストすることに頼らざるを得ませんでした。

非常によく似た問題について説明している記事をいくつか見つけましたが、特に2とは異なるベースで、実際の実装に焦点を当てているものはありません。これは、数値が内部に格納される方法によるものと思われますが、前述のアルゴリズムは、たとえば、それを考慮しても、b=10です。私も他の人に連絡しようとしましたが、やはり役に立ちませんでした。

したがって、私の質問は次のようになります。前述のアルゴリズムが説明されている記事や本などがあり、実装について説明している可能性がありますか。そうでない場合、たとえばC / C ++でそのようなアルゴリズムを実装してテストすることは理にかなっていますか、それともこのアルゴリズムは本質的に悪いのでしょうか？

また、私はプログラマーではありません。プログラミングはかなり大丈夫ですが、確かにコンピューターの「内部」についてはあまり知識がありません。したがって、私の無知を許してください-この投稿には1つ以上の非常に愚かなことがある可能性が高いです。もう一度ごめんなさい。

どうもありがとう！

コメント/回答で提起されたポイントのさらなる明確化：

みなさん、ありがとうございました。すばらしい回答やアドバイスをすべて同じものでコメントしたくなかったので、多くの方が触れた1つのポイントについてお話ししたいと思います。

私は、ベース2 ^ nでの作業が、一般的に言って、明らかに最も効率的な方法であることを十分に認識しています。ほとんどすべてのbigintライブラリは2^32などを使用します。しかし、もし（そして、私が強調するのは、この特定のアルゴリズムにのみ役立つでしょう！）、基数bの数字の配列としてbigintsを実装するとどうなるでしょうか？もちろん、ここではbが「合理的」である必要があります。最も自然なケースであるb = 10は、十分に合理的であるように思われます。数値が内部に保存される方法を考慮すると、メモリと時間の両方を考慮すると、多かれ少なかれ非効率的であることはわかっていますが、私の（基本的でおそらく何らかの欠陥のある）テストが正しければ、GMPの一般的な区分よりも速く結果を生成することができました。これは、そのようなアルゴリズムを実装することに意味があります。

Ninefingersは、その場合、高価なモジュロ演算を使用する必要があることに気づきました。古い+新しい+1の桁数を見るだけで、古い+新しいがたとえば999と交差したかどうかを確認できます。4桁の場合は、これで完了です。さらに、old<999およびnew<= 999であるため、old + new + 1が4桁の場合（これ以上持つことはできません）、（old + new）％999は（の左端の桁を削除することになります） old + new + 1）、これは安くできると思います。

もちろん、私はこのアルゴリズムの明らかな制限に異議を唱えていませんし、改善できないと主張していません-それは特定のクラスの数でしか分割できず、ベースbでの配当の表現を事前に知っている必要があります。ただし、たとえばb = 10の場合、後者は自然に見えます。

さて、上で概説したように、bignumを実装したとしましょう。ベースbでC=（a_1a_2 ... a_n）、D = b^k-1と言います。アルゴリズム（おそらくはるかに最適化されている可能性があります）は次のようになります。タイプミスが少ないといいのですが。

• k> nの場合、明らかに完了です
• Cの先頭にゼロ（つまりa_0 = 0）を追加します（たとえば、9999を99で除算しようとする場合に備えて）
• l = n％k （「通常の」整数のmod-高すぎないようにする必要があります）
• old =（a_0 ... a_l）（最初の数字のセット、おそらくk桁未満）
• for（i = l + 1; i <n; i = i + k）（floor（n / k）程度の反復があります）
  • new =（a_i ... a_（i + k-1））
  • new = new + old （これはbigintの追加であるため、O（k））
  • aux = new + 1 （繰り返しますが、bigintの追加-O（k）-私は満足していません）
  • auxがk桁を超える場合
    • 補助の最初の桁を削除します
    • old = old + 1 （もう一度bigint加算）
    • 古いものを最初にゼロで埋めて、必要な桁数になるようにします
    • （a_（ik）... a_（i-1））= old （i = l + 1の場合、（a _ 0 ... a _ l）= old）
    • new = aux
  • newを最初にゼロで埋めて、必要な桁数になるようにします
  • （a_i ... a_（i + k-1）= new
• quot =（a_0 ... a_（n-k + 1））
• rem = new

そこで、これについて私と話し合ってくれてありがとう-私が言ったように、これは、致命的な欠陥が見当たらない場合に、実装、テスト、および議論を試みる興味深い「特殊なケース」のアルゴリズムのようです。これまで広く議論されていないものであれば、さらに良いでしょう。ご意見をお聞かせください。長い投稿でごめんなさい。

また、もう少し個人的なコメント：

@Ninefingers：私は実際にGMPがどのように機能するか、それが何をするか、そして一般的なbigint除算アルゴリズムについてある程度の（非常に基本的な！）知識を持っているので、あなたの議論の多くを理解することができました。また、GMPが高度に最適化されており、さまざまなプラットフォームに合わせてカスタマイズされていることも承知しています。そのため、一般的に「打ち負かそう」とはしていません。これは、先のとがった棒で戦車を攻撃するのと同じくらい実り多いようです。ただし、これはこのアルゴリズムの考え方ではありません。非常に特殊な場合に機能します（GMPではカバーされていないようです）。無関係なことに、一般的な分割はO（n）で行われていますか？私が見た中で最も多いのはM（n）です。（そして、私が正しく理解していれば、実際には（Schönhage–Strassenなど）O（n）に到達しない可能性があります）。それでもO（n）に到達しないフューラーのアルゴリズムは、私が正しければ、ほぼ純粋です。理論的。）

@Avi Berger：考え方は似ていますが、これは実際には「九去法」とまったく同じではないようです。しかし、私が間違っていなければ、前述のアルゴリズムは常に機能するはずです。

Javaで整数間の除算を実行する必要があり、結果はfloatになります。

/シンボルを使用できますか？のように：

私は固定小数点演算のクラスを持っていますが、これが重要な部分です。

GCC 4.4.5では、次のコード行があります。

エラーを生成します：

コードには定数ゼロによる除算がありますが（スケールが等しくない場合はT/SまたはS/Tのいずれかがゼロである必要があります）、S％T == 0（およびSが0でない）の場合、S/Tはゼロではありません。GCCは、私のブランチの1つがゼロ除算であることが保証されていることを理解するのに十分な最適化を行っているようですが、そのブランチが実行されないことが保証されていることを理解するのに十分な最適化ではありません。

ファイルをスロー#pragma GCC diagnostic ignored "-Wdiv-by-zero"することはできますが、実際の警告を隠すリスクがあります。

この状況に対処するための適切な方法は何ですか？（または、私の分析は完全に間違っていて、実際の実行時のゼロ除算はありますか？）