- ベストアンサー
べき乗
大学のレポート課題ですが、自然数m, nで、mのn乗を求める効率の良いプログラムを考えています。 ヒントには、「n=64であれば6回の乗算で計算できる」とあります。 n=64のとき、乗算6回で計算するプログラムは出来ましたが、nの値を変えると間違った答えが出ますし、それを考慮して作ったプログラムもnの値によって正解だったり、不正解だったりします。 いくつも考えますたが、どれもそんな状況なので質問させていただきました。分かった方はどうか教えてください。 （回答は、出来る限りJAVAかCでお願いします。）
- myst_scientist
- お礼率55% (24/43)
- その他（プログラミング・開発）
- 回答数5
- ありがとう数2
- みんなの回答 （5）
- 専門家の回答
関連するQ&A
- 乗算回数最小の冪乗アルゴリズム
断面ｎ次モーメントを計算するプログラムを書いていてふと思ったのですが， X^n を乗算の繰り返しで計算する場合，一般の自然数ｎについて乗算回数最小の アルゴリズムって存在するんでしょうか？ たとえばｎが２の冪乗の場合，２乗を繰り返すと１回ごとに X → X^2 → X^4 → X^8 → X^16 → … となるので，X^n は log2(n) 回の乗算で計算でき，たぶんこれが最小だと思います． その他のｎについてはどうでしょうか？ ｎの素因数分解とか使えばうまくいくんでしょうか？
- ベストアンサー
- 数学・算数
- ｃ言語による２のべき乗
右、左シフトと２のべき乗による乗除算が同じことを証明するプログラムを作っているのですがうまくいきません。 プログラムを載せるのでどこが間違っているのかご教授お願いします。 #include <stdio.h> int count_bits(unsigned x){ int count = 0; while(x){ if(x&1U) count++; x>>=1; } return(count); } int int_bits(void){ return(count_bits(~0U)); } void print_bits(unsigned x){ int i; for(i=int_bits()-1; i>=0; i--) putchar(((x>>i)&1U) ? '1' : '0'); } int main(void){ unsigned nx, no, n1, n2; printf("非負の整数を入力してください："); scanf("%u", &nx); printf("何ビットシフトしますか？："); scanf("%u", &no); n1=nx * (2^no); n2=nx / (2^no); printf("\n整数 ＝ "); print_bits(nx); printf("\n左にシフトした値 ＝ "); print_bits(nx << no); printf("\n右にシフトした値 ＝ "); print_bits(nx >> no); printf("\n２のべき乗で乗算した値 ＝ "); print_bits(n1); printf("\n２のべき乗で除算した値 ＝ "); print_bits(n2); putchar('\n'); return(0); }
- ベストアンサー
- C・C++・C#
- javaでべき乗余
テストプログラムとしてjavaでべき乗余を求めるプログラムを作っているんですがint N の大きさを大きくするとかなり時間がかかってしまいます。実行時間を早くする方法はないでしょうか？ import java.math.BigInteger; import java.util.Random; public class s1{ public static void main(String args[]){ BigInteger a = new BigInteger("2"); int N = 100000; BigInteger n,p,q; Random rnd = new Random(); BigInteger f[] = new BigInteger[N]; int bit = 512; int k = 10; p = new BigInteger(bit,k, rnd); q = new BigInteger(bit,k, rnd); n = p.multiply(q); int j; for(j=0;j<N;j++){ f[j]=(a.modPow(BigInteger.valueOf(j), n)) ; } for(j=0;j<N;j++){ System.out.println(j +"="+f[j]); } } }
- ベストアンサー
- Java
- パソコンで階乗を計算
現在、fortran90を使って階乗を計算するプログラムを作っております。 プログラム内容は、(n !を求めえるプログラム) n=0 do i=1,100 n=n*i enddo このプログラムを実行すると、１２！までは予想された値が得られるのですが、１３！以降は電卓で計算した値と遙かに異なる値が得られました。 このプログラムは間違っているとは思えないですが、電卓の計算とパソコンの計算が異なる結果になった理由が分かりません。 どなたか、ヒントや参考情報だけでもいいので教えてください。 ちなみにパソコンによる計算結果は、 i n 1 1 2 2 3 6 4 24 5 120 6 720 7 5040 8 40320 9 362880 10 3628800 11 39916800 12 479001600 13 1932053504 14 1278945280 15 2004310016 16 2004189184 17 -288522240 18 -898433024 19 109641728 20 -2102132736 21 -1195114496 22 -522715136 23 862453760 24 -775946240 25 2076180480 26 -1853882368 27 1484783616 28 -1375731712 29 -1241513984 30 1409286144 31 738197504 32 -2147483648 33 -2147483648 34 0 35 0 36 0 36の階乗以降０です。 計算結果が正となるが、結果が違うモノ（例えば、１３！や３１！）は単精度で約１０桁程度しか有効数字が得られないためであると思われるのですが、負になったり、０になる理由が分かりません。
- 締切済み
- その他（プログラミング・開発）
- Verilogでモンゴメリ乗算
私はVerilogについてはド素人で全くと言っていいほど書くことができません。そこに仕事上でVerilogでモンゴメリ乗算をしなくてはならなくなりました。どうかわかる方はこの以下のアルゴリズムを利用してプログラムを教えてください。お願いします。 まずはそのアルゴリズムを紹介します。 [モンゴメリ乗算アルゴリズム] Input: N,0<A<N,0<B<N,V 前計算: V=-N-1mod2r output: M=A・BmodN Step 1:Q=A・B・VmodR R=2r Step 2:M=AB+QN Step 3: M=M/R 注．前計算,step1の2rは“2のr乗”です。また前計算の-N-1は “-Nの-1乗”のことです。 ビット数は全て8bitでお願いします。
- 締切済み
- その他（プログラミング・開発）
- FE（H24秋試験） 問７の問題
以下の問の答えがnになる理由がなかなか分からず ネットで探してみたんですが、わかりやすい解説を見つけられませんでした。 かみくだいて、ぜひ教えていただきたいです。 よろしくお願いします 問７ n！の値を、次の関数F（n）によって計算する。 乗算の回数を表す式はどれか。 F（n）＝ １ （n＝０） ＝ n×F（nー１） （n＞０） ア n-１ イ n ウ n＾2 エ n！ 私は、例えば、n＝４の場合だと ４×３×２×１ なので掛け算の回数は３回になっていると思い、「ア」を 選びましたが、回答は「イ」でした。 分かりやすい解説をお待ちしています。
- ベストアンサー
- その他([技術者向] コンピューター)
- 行列をべき乗させるプログラム
2行2列を５乗させるプログラムを作って、一応できたつもりだったんですが結果が合いません・・・ 何かヒントでもいいのでわかる方いらっしゃいましたらよろしくお願いします。 <プログラム> #include <stdio.h> #define N 2 int A[N][N]; int A_NEW[N][N]; int A_5[N][N]; /* 行列Aを５乗したもの */ int main() { int i,j,k,l; /* 2行2列の係数行列Aの成分を入力 */ printf("係数行列Aを%d行%d列で入力してください\n", N, N); for( i=0; i<N; i++) { for( j=0; j<N; j++) { printf("A[%d][%d]=", i+1, j+1); scanf("%d", &A[i][j]); } } for(i=0; i<N; i++) /* A_NEW=A*Aの計算 */ { for(j=0; j<N; j++) { for(k=0; k<N; k++) { A_NEW[i][j] += A[i][k] * A[k][j]; } } } for(l=0; l<3; l++) { for(i=0; i<N; i++) /* A_5の計算 */ { for(j=0; j<N; j++) { for(k=0; k<N; k++) { A_5[i][j] += A_NEW[i][k] * A[k][j]; } } } for(i=0; i<N; i++) { for(j=0; j<N; j++) { A_NEW[i][j] = A_5[i][j]; } } } printf("A_5=\n"); /* 出力 */ for( i=0; i<N; i++) { for( j=0; j<N; j++) { printf("%d ", A_5[i][j]); } printf("\n"); } } <入力例> A= 1 3 2 1 <期待する結果> A= 241 303 202 241 <このプログラムの結果> 406 498 332 406
- ベストアンサー
- C・C++・C#
- 流れ図について
「自然数m,nに対して、mのn乗を計算する効率のいいアルゴリズムを流れ図を記述せよ（n＝６４のとき、乗数の回数は６回ですむ）」って問題がでたのですが答えられずわからなかったのですが、効率のいいアルゴリズムを流れ図で書くことはできるのでしょうか？宜しくお願い致します。
- 締切済み
- その他（プログラミング・開発）
- 数当てゲームについて（べき乗のあらわし方）
#include<stdio.h> #include<time.h> #include<stdlib.h> int main(void) { int limit=0; int no1,no2,no3; /*当てさせる値*/ int num; /*入力する値*/ int max=15; srand(time(NULL)); no1=rand(); no2=rand(); if(no1>no2) { do{ no3=rand()%(no1+1); }while(no3<no2); } else if(no1<no2) { do{ no3 = rand()%(no2+1); }while(no3<no1); } if(no1>no2) { if(num<no2 || num>no1) { printf("%d以上%d以下の数字を入力してください。\n",no2,no1); } } else if(no1<no2) { if(num<no1 || num>no2) { printf("%d以上%d以下の数字を入力してください。\n",no1,no2); } } do{ printf("あと%d回入力できます。数字を入力してください。\n",max-limit); scanf("%d",&num); limit++; if(num>no3) { printf("大きいです。\n"); } else if(num<no3) { printf("小さいです。\n"); } }while(num!=no3 && limit<max); if(num==no3) { printf("正解です。"); printf("%d回で当たりました。",limit); } else { printf("残念ながら不正解です。正解は%dでした。",no3); } return 0; } このプログラムは制限回数以内でランダムで入力した値を 当てさせるものです。 当てさせる数であるランダム値の範囲としましては、ランダムで 二つの値を入力して「小さいランダム値以上大きいランダム値以下」 です。 そして、その範囲内で制限回数以内に当てさせるというものです。 ここで質問なのですが、「制限回数を2のべき乗以内とするにはどうすれば いいのかということです。」 たとえば、 ランダム値が2000と2004が入力されたとしたら、お互いの差は4であり 二分検索法の平均検索回数の式「log2n」というものを使うと2回とするのが 検索回数として妥当であると考えるからです。 当てさせる数が 8以内ならば3 16以内ならば4 32以内ならば5 という形で制限回数が増えていくようにしたいです。 2^n<max<2^(n+1) ^はべき乗をあらわします。 上記のような式ならば、制限回数がn+1になるようにです。 プログラムの中では、制限回数をmaxとしています。 ですが、上記のようなあらわし方がよくわからなかったので、 max=15と暫定的に定めてあるだけです。 長くなりましたが、よろしくお願いいたします。
- 締切済み
- C・C++・C#
- このプログラムはどのように作成するのでしょうか？
プログラム作成について勉強しているのですが、分からないのでぜひ教えていただきたいです。 整数Mと初期値X(0)の値を入力し、 X(n+1)=16807X(n) をN=Mまで計算しファイルX.dataに書き出すプログラムを作成 (X(n)は倍数度実数) 分かる方、ぜひご教授ください。
- ベストアンサー
- その他（プログラミング・開発）
お礼
皆さん、ありがとうございます。 完成とまでは行っていませんが、自分のプログラムのまずかった点と、方法の検討がつきました。