5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

プログラミングの為の数学と算数

1 :デフォルトの名無しさん:2001/08/07(火) 11:19
数学(まあ算数の範囲も含めよう)的な問題のTIPS/Q&Aスレです

個別にあるとすぐに下がってしまうのでこの領域の話題をまとめましょう

関連スレ>>2

2 :デフォルトの名無しさん:2001/08/07(火) 11:19
フーリエ変換について教えてください
http://piza2.2ch.net/test/read.cgi?bbs=tech&key=996929748

交差判定アルゴリズム
http://piza2.2ch.net/test/read.cgi?bbs=tech&key=996157997

サウンドプログラミング
http://piza2.2ch.net/test/read.cgi?bbs=tech&key=996171508

最速の素数判定アルゴリズム 
http://piza2.2ch.net/test/read.cgi?bbs=tech&key=993457354

公開鍵の高速な生成
http://piza2.2ch.net/test/read.cgi?bbs=tech&key=991992977

3 ::2001/08/07(火) 11:28
早速だけど、
非力なCPUで対数を計算させたいのです。
log(a)を求めるのに、a=b*2^n として
bを0.5〜の範囲に調整し
x = 1-b として(xは0〜0.5の範囲)
ln(b) = -(x+x^2/2+x^3/3+x^3/4+x^5/5+x^6/6+x^7/7)

さらに高速なのは
x=(1-b)/(1+b) として(xは0〜0.333の範囲)
ln(b) = -2*(x+x^3/3+x^5/5+x^7/7+x^7/9)
log(b) =-0.86859*(x+x^3/3+x^5/5+x^7/7+x^7/9)

というのは考えました。
これでまあなんとかなりそうだけど、

c=log(a)が求まっている時に aとそう違わないa'に対して
c'=log(a') をもっと効率的に求める方法は無いでしょうか?

つまりニュートン法みたいに、ある計算をすると精度が
少し上がるような計算方法は無いでしょうか?

ニュートン法をそのまま適用するとexp(x)を計算しなけりゃ
いけないようなのですが、これを巧く消す方法が無いかな?

4 ::2001/08/07(火) 11:33
具体的な応用は、いわゆるスペアナみたいなものなんで、
精度は少数以下6ビット程度です。
 (だから前回の結果とはそんなに極端には変わりません)

最悪テーブルを引く方法でもいいのですが、メモリ
も極小なので巧い計算方法があればという所なんです。

5 :デフォルトの名無しさん:2001/08/07(火) 12:15
俺は差し迫って必要ってわけでもないので
ゆっくり勉強するのだ。
大学受験もあるしな。

6 :デフォルトの名無しさん:2001/08/07(火) 14:05
>>3
除算がそれほど苦じゃないなら 0.5〜1にした後で
√0.5以下なら√0.5で割ってから級数展開すれば収束が早くなるよ
後でlog(√0.5)を足せばいい。

あるいは平方根(lこれはニュートン法3回程度で十分)出してから
級数展開してもいいし

テーブルを作る方法でも、荒いテーブルを作っておいて
補間する方法でいいんじゃないの?
log(x)の傾きは1/xだから、これで補間してもそれなりの精度出るでしょ。

7 ::2001/08/07(火) 14:24
>>6 レスありがとうございます。

色々考えてみて、やっぱり逐次的に精度が上がる方法は難しいようです。
テーブルを補間する方法で考えてみます

8 ::2001/08/07(火) 14:25
CPUは除算命令は持ってるけど24クロックかかるという奴なんで除算も苦しいです

9 :デフォルトの名無しさん:2001/08/07(火) 16:01
前から気になってた事があるんだけど、

ニュートン法で逆数を計算するって
ttp://member.nifty.ne.jp/kaz1-iwata/divsqrt.htm

Xi+1 = Xi * (2 - b*Xi)
これで、実際計算は出来るんだけど、これってどうやって導いたの?

x*b=1 から x*b-1=0とおいて 微分して b
x-f(x)/f'(x) = x- (x*b-1)/b = x-x+1/b =1/b になっちゃうんだけど?

10 ::2001/08/07(火) 18:55
log(a)を求める方法ですが、a=b*2^n として
bを0.5〜1の範囲に調整し
log(a)= -0.933*b*b + 2.775*b -1.8437 + log(2)*n

で求める精度が出ました

>>9
>x*b=1
じゃなくて
b=1/x から b-1/x としてやったらどうでしょ?

11 :9:2001/08/07(火) 20:20
>>10 うわぁ 恥じぃ そういう事か。。。。

12 :デフォルトの名無しさん:2001/08/08(水) 01:18
こういう話題って数学板が参考になるかも

13 :デフォルトの名無しさん:2001/08/09(木) 22:51
最近のプログラムって数学使わないのかな?

14 :デフォルトの名無しさん:2001/08/09(木) 22:53
IE6でMathMLに対応していれば、数学の教科書作りたいと思っているけど、
その辺知ってる?

15 :コメント無しさん:2001/08/09(木) 23:40
>>13
昔は使ってたのか?
プログラム技術は数学使うけどプログラム自体には数学使わないような気が。

16 :デフォルトの名無しさん:2001/08/09(木) 23:51
IE6ではMathML対応してないんじゃないかなぁ。

17 :デフォルトの名無しさん:2001/08/10(金) 02:01
MathMLに対応してるのはAyamaくらいでは。

18 :デフォルトの名無しさん:2001/08/10(金) 02:28
age

19 :デフォルトの名無しさん:2001/08/10(金) 03:25
>>15
ド・モルガンの法則とか、その程度かねえ。

20 :デフォルトの名無しさん:2001/08/10(金) 03:32
ラ・セーヌの☆

21 :デフォルトの名無しさん:2001/08/10(金) 06:40
DSPのプログラムするのに、数式とか弄る方だと思うんだが
mathCadとか使うからもはや自力じゃ何にも解けないな
因数分解とか2次方程式の解とかみんなオマカセさ

解いて欲しい問題あったら出してみてよ

22 :双六野郎:2001/08/11(土) 21:27
双六で、上がりまでnマスの位置に居るとき、何回ダイスを振ればあがれるか?
ぴったり上がりにはいらなくても(行き過ぎても)ok。ダイスの目は1〜6。
n=1 なら 1.000000000 回
n=2 なら 1.666666666.. 回
n=50なら14.761904780.. 回
帰納的解法で解いたけど、一発解の出し方がわからない。
綺麗な一発解があるはずなんだけど...どお?

23 :双六野郎:2001/08/11(土) 21:31
あ、何でプログラミングの為の数学かというと、私が
帰納的解法をプログラムで使っているからです。
そのプログラムは、フリーの双六ゲームです。とほほ..

24 :デフォルトの名無しさん:2001/08/11(土) 21:37
ひさびさに面白そうなお題だね。
ちょっと考えてみよう

25 :デフォルトの名無しさん:2001/08/11(土) 21:43
n=2で1.66666回?

26 :デフォルトの名無しさん:2001/08/11(土) 22:09
E(x<=0)=0 として、
E(n) = 1 + 1/6*(E(n-1)+E(n-2)+E(n-3)+E(n-4)+E(n-5)+E(n-6))
になったりする?

27 :双六野郎:2001/08/11(土) 23:15
>25
失礼。
n=2で1.16666..の間違いでした。
>26
そのとおり。それが「帰納的」解法だね。
(E(n)を求めるためにはE(n-1)が必要)
int goal(n)
{
int i;
double cast[51];
for(i=0;i<n;i++)
cast[i]=0;
for(i=1;i<n;i++){
for(j=i-1;j>=0;j--){
if((i-j)>6) break;
cast[i]+=cast[j];
}
cast[i]/=6;
cast[i]++;
}
return cast[i];
}
どう?美しくないでしょ?
さて、一発解は有るかな?

28 :デフォルトの名無しさん:2001/08/11(土) 23:25
単に期待値 3.5 で割るだけじゃだめなの? >>27
50/3.5 で大体 14 ぐらいだけど、

もしかして罠はってる?

29 :双六野郎:2001/08/11(土) 23:41
>27 (自己レス)
ありゃ?関数がint型に。jも宣言してない。おまけに返すのは(引数-1)の解だ。大変失礼をば。
>28
n→∞ならE(n)はn/3.5に収束しますね。でも、n=1の場合は、明らかにE(n)=1/3.5じゃ無いですよね。
サイの目は下限の有る離散数で、おまけに上限まで有るからやっかいですなぁ。

30 :26:2001/08/11(土) 23:50
E(n+1)=7*E(n)/6 - E(n-6)/6
だから(E(n+1)-E(n)を計算)
プログラムはもう少し簡単になるのではないでしょうか?

31 :双六野郎:2001/08/12(日) 00:20
>30
おお。シンプルですね。素晴らしい。解けそうな予感。

ちょっと解説。
私の言ってる「一発解」を説明しますと、
例えば、E(O)=0 かつ E(n)=E(n)+1
の場合、E(n)=n ですよね。
このように、E(n)を求めるのに、E(n-i)
を必要としないやりかたは無いものかと..

32 :28:2001/08/12(日) 00:23
なるほどわかった、バカだな>自分

33 :双六野郎:2001/08/12(日) 00:28
訂正
X : E(n)=E(n)+1
O : E(n+1)=E(n)+1
また、一発解があったとして、実際にコーディングする際には、pow(6,n-1)が
入ってきそう。doubleでも無理かな。コーディング注意ですね。

34 :26:2001/08/12(日) 00:38
乱暴だが、
E(n+1)=r * E(n) (1<r<7/6)
のような近似式にして、等比級数を出してしまうとか。

35 :デフォルトの名無しさん:2001/08/12(日) 01:22
ねえねえ、夜中の通販番組で売っている、

「アーサー・ベンジャミン教授のMath Magics」

って買った人いる?あれってなにかのアルゴリズムに役立つのでは
なかろうか。(ネタ半分、マジ半分)。

外出だったらすまんこ。

(Math Magicsとは、「ある数の全部の桁を足して3の倍数になったら
その数は3の倍数である」みたいな知識をたくさん集めて、暗算を早くやろう、
という教材です。)

36 ::2001/08/12(日) 11:10
>>22
チラっと見た感じで、近似式は

n /3.5 + 10/21 + sin(2*π*n/6+φ)/EXP(a*n+b)

n=50程度迄で1割程度の精度の近似係数は
φ=0
a=1
b=0
sin,の位相や指数の係数を調整すればもっと精度上がると思う

37 ::2001/08/12(日) 11:25
>>35

プログラマ向け?

1)偶数か奇数かは LSBを見よ
2) a MOD 2^n は a AND 2^n-1 で計算せよ
3) 3で割った余りは a=(a>>2+a & 3) を繰り返せ
4) 7で割った余りは a=(a>>3+a & 7) を繰り返せ
5) a*2^n は a <<n で計算せよ
6) a/2^n は a >>n で計算せよ

みたいな感じかなあ? もはや不要なテクニックだろうけどね

38 ::2001/08/12(日) 11:35

正確に求めるには Z=1/z として Z変換

        1
--------------------------
1-(Z+Z^2+Z^3+Z^4+Z^5+Z6)/6

を解けばよいのかな?

39 :デフォルトの名無しさん:2001/08/12(日) 11:45
>>37
CなのかBasicなのかわからん(w

40 ::2001/08/12(日) 12:02
38は間違いだね
>E(n+1)=7*E(n)/6 - E(n-6)/6
だから 1/(1-7/6Z+Z/6) かな?

>>39 ごめん

41 :双六野郎:2001/08/12(日) 12:49
22です。
おお、参考になる。みなさん有難う。
>>36
sinが入るんですか。
振動はしないと思っていたので意外。フーリエ変換の結果でしょうか?
たしかに、n={7,13,19,...}で特異な点が出現しますなあ。
収束E(n)/nは収束するから、expが入るのはなんとなく理解。

42 ::2001/08/12(日) 14:01
>>41 フーリエ変換はしてないけど、Excelで表を書くと振動が見えたし
   とりあえずZ変換に出来そうだから、線形だと思う。
  だから、振動項と指数減衰項があれば良い近似が出来そうというのが直感

 φ=0 は間違いで 90°つまりcos(2πn/6) にしてみて

 オフセットは 10/21でいいと思うけど検算してね

43 ::2001/08/12(日) 14:45
自分で検算しました。

n/3.5+10/21+ sin(2*M_PI/24*(n*4+2)) /exp(n-1)*0.238095
n 誤差
1 +0
2 -0.07
3 -0.04
4 +0.02
5 +0.05
6 +0.03
7 -0.05
8 -0.01
以下どんどん誤差は小さくなります。
これで実用的には十分だと思います

44 ::2001/08/12(日) 15:38
さらに、係数を調整してもあまり精度が向上しません。

もっと精度が必要なら
n/3.5+10/21+ cos(2*M_PI*(n-1)/6)/exp((n-1)*A)*B + sin(2*M_PI*(n-1)/6)/exp((n-1)*C)*D

としてA,B,C,Dの係数を調整すると良いと思います


近似式がこういう格好をしてるので、正確な解は簡単な表現では出来ないように思います

45 :双六野郎:2001/08/12(日) 16:25
1さんへ。感謝です。
なるほど、私には十分な精度です。
厳密解がなさそう と解ったこともおおきな収穫でした。
2chって素晴らしい。

46 :26:2001/08/12(日) 16:33
数学板で聞いてみたらあっさり答えを出してくれた。
特性方程式の一般化みたいなことをやるみたいだ。

-----
E↑(n) = [E(n), E(n-1), E(n-2), E(n-3), E(n-4), E(n-5), E(n-6)]
と置くと、
E↑(n+1) = A・E(n)
だから
E↑(n) = A^(n-1)・E(1)

Aは7×7の行列で、
A11 = 7/6, A17 = -1/6
A21 = A32 = A43 = A54 = A65 = A76 = 1
それ以外の要素は0。

Aのn乗は自力で計算してね。
-----
Aのn乗はO(log n)の計算で出来るし、
疎な行列なのでうまくやれば軽いコードになると思う。

47 :双六野郎:2001/08/12(日) 16:47
>46
美しいですね。
要素を見ると正解の予感がするんですが、
"↑"の記号の意味を知らない自分が悲しい。
修行してきます。

48 :26:2001/08/12(日) 16:52
縦のベクトルです。
あ、
E↑(n+1) = A・E↑(n)
E↑(n) = A^(n-1)・E↑(1)
の間違いかな。

49 :26:2001/08/12(日) 16:54
漸化式が線形だから、線形代数で解けるのは当たり前なのか…。
似たような問題は同様の行列をつくれば解けるということみたい…。

50 ::2001/08/12(日) 16:56
たぶん ↑はベクトルにするという事でしょう
E(n-6)〜E(n) の 7個の要素を持つベクトルを E↑(n)と書くという事だと思います

この表現は、>>26 や >>30 の表現と意味は同じだけど
行列のn乗は 2進分解すれば高速に計算出来るという仕掛けが利用出来ると
いう事だと思います

51 :双六野郎:2001/08/12(日) 17:02
>48
26さん、ご親切痛み入ります。
了解しました。7行1列の行列ということですね?
やってみます。
>うまくやれば軽いコードになると思う。
これは自信ありません。
27に書いたものに限りなく近くなりそうで恐い。

52 :双六野郎:2001/08/12(日) 17:12
次から次へと、ここは知識の宝庫ですね。
"↑"が解ったら今度は"2進分解"が解らない。
googleで調べても論文のインデックスが1件だけ。
日本語じゃだめか。"binary partition"で良いですか?

53 ::2001/08/12(日) 17:24
>>52
たとえば a^8 を計算するのにaに7回aを掛けるかわりに
a^2^2^2 と計算します
つまり a2=a*a a4=a2*a2 a^8=a4*a4 と3回に分けて計算します

つまり a^n のnを2進数で表現してべきを高速に計算する方法の事です

54 :26:2001/08/12(日) 17:25
例えば、
X^4=(X*X)*(X*X)=(X*X)^2
で掛け算が2回で済みますってことでしょう。
つまり、
A^(2^x)の値を計算しつつメモリに置いておけば
A^nのnが大きいときでも
A^(2^x1+2^x2+....)とすることにより
計算の手間が減るということです。
また、A^nは上三角行列に似た(1つ下にずれてる感じだが)
行列になります。

55 :双六野郎:2001/08/12(日) 17:34
検索に疲れて帰ってきてみれば...
有難うございます。たしかに速いし、
有効桁あふれのチェックも兼ねられそう。
この2日間でずいぶん賢くなりました。
重ねて感謝。

56 ::2001/08/12(日) 17:38
バイナリ法(2進分解)が使えるとしても、行列の2乗は結構重い処理です。
nが小さい時には、あまり意味が無いでしょう。

n>12 なら 近似式 n/3.5+10/21 で良い精度の答えになりますから

実用的には n<=12 で>>26の計算を使うかテーブルを引き
n>12 で n/3.5+10/21 を使うという方法が一番効率的かと思います

57 ::2001/08/12(日) 18:02
12は見間違いでした

n E(n) 近似値 誤差 近似値= n/3.5+10/21
10 3.324  3.333  +0.010
11 3.613  3.619  +0.006
12 3.906  3.905  -0.002
13 4.197  4.190  -0.007
14 4.476  4.476  +0.000
15 4.760  4.762  +0.002
16 5.046  5.048  +0.001
17 5.333  5.333  +0.000
18 5.620  5.619  -0.001
19 5.905  5.905  -0.001
20 6.190  6.190  +0.000

58 :デフォルトの名無しさん:2001/08/12(日) 21:36
プログラマだからどうしても真の値より不正確でも速い方法に走ってしまうんだね

なんか面白いな

59 :双六野郎:2001/08/12(日) 21:55
最初は真の値の方に興味があったんですけどね。
近似は近似で奥が深い。sinの中身が6周期になる所なんか、宇宙の意思ですね。
ちなみに、私の作った双六ソフトは本双六と呼ばれる平安期に流行ったもので、
n は最大19です。その代り、15個の石をあやつるので、どっちが優勢かの判別が
難しい。そこで27に書いたような方法でインジケーターをつけました。

60 :デフォルトの名無しさん:2001/08/12(日) 22:19
>59
n<20なら27の方法でサイズ・速度ともに十分だろうに。
(ただし、配列は6要素で循環再利用するのがエコロジカルよ。)
そこで一般解が気になるあたりが数学の魔力か。

61 :60:2001/08/12(日) 22:21
ところで、本双六ってなに?
石が15個って、自分の駒が15個ってこと?

62 :デフォルトの名無しさん:2001/08/13(月) 04:36
これって >>30 の方法だと
double goal(int n)
{
int i;
double a[7]={1,0,};
double r=1;
for(i=1;i<n;i++)
 {int j=i%7;
  r+=(r-a[j])/6.0;
     a[j]=r;
 }
return r;
}
だから、真面目に計算しても十分だよな

63 :デフォルトの名無しさん:2001/08/13(月) 06:34
>>61
これだ、バックギャモンっぽいものらしー

64 :デフォルトの名無しさん:2001/08/13(月) 06:36
http://www.vector.co.jp/soft/win95/game/se081546.html
貼り忘れた、逝ってくる

65 :デフォルトの名無しさん:2001/08/13(月) 06:59
もうひとつ。
vectorには>>63とこれの2つしかないな。
http://www.vector.co.jp/soft/win95/game/se202098.html

66 :デフォルトの名無しさん:2001/08/13(月) 07:46
前回との差だけ前後させる方法でやったらどうだと思ったが
 doubleだと計算誤差で元に戻れない
  long doubleでも誤差1%チョット出るな

long double a[7];
int pg;
int n;
init() { pg=0;for(int i=0;i<7;i++)a[i]=0;a[0]=1;n=1;};
double inc(){
long double r=a[pg];
 pg=(pg+1) % 7;
 r+=(r-a[pg])/6.0; //E(n ) =E(n-1) + (E(n-1)-E(n-7))/6
 a[pg]=r;
 n++;
return r;
};
double dec(){
int pg0=pg;
long double r,r0=a[pg];
 pg=(pg+7-1) % 7;
 r=a[pg];
 a[pg0] = r*7-r0*6;
  n--;
  return r;
};

double goal(int m)
{ while(n>m)dec();
 while(n<m)inc();
 return a[pg];
}

67 :デフォルトの名無しさん:2001/08/13(月) 07:51
× a[pg0] = r*7-r0*6 ;   これを
○ a[pg0] = r+(r-r0)*6.0;  こう修正すると1桁精度が上がった

68 :デフォルトの名無しさん:2001/08/13(月) 09:20
>>66
n<50 なら10万回繰り返しても精度落ちなかったから何の事かと思ったけど
n=100付近から戻れなくなるんだね

69 :デフォルトの名無しさん:2001/08/13(月) 10:06
>>66 ひとつの関数にまとめとこう

double goal(int m)
{
static long double a[7]={ 1 , 0 , };
static int pg=0;
static int n=1;
 while(n<m) {
 long double r=a[pg];
  pg=(pg+1) % 7;
  r= r+ (r-a[pg])/6.0;
  a[pg]=r;
  n++;
 }
 while(n>m){
 int pg0=pg;
 long double r;
  pg=(pg+7-1) % 7;
  r=a[pg];
  a[pg0] = r+(r-a[pg0])*6.0;
  n--;
 }
 return a[pg];
}

70 ::2001/08/13(月) 11:28
精度の問題を解決するには、 E(n)の代わりに R(n)=E(n)-n/3.5-10/21 とすれ
ばいい。 こうすればR(n)はnに応じて値が小さくなり、浮動小数点なら情報落ち
が少ない。

すぐに判るように R(n)はE(n)と同じ式になる。
初期値だけを変更すればいい。


double goal(int m)
{
#define c0 (10.0/21.0)
static double a[7]={1.0-1.0/3.5-c0,0-c0,1.0/3.5-c0
,2.0/3.5-c0 ,3.0/3.5-c0 , 4.0/3.5-c0 , 5.0/3.5-c0};
static int pg=0;
static int n=1;
 while(n<m) {
 double r=a[pg];
  pg=(pg+7-1) % 7;
  r= r+ (r-a[pg])/6.0;
  n++;
  a[pg]=r ;
 }
 while(n>m){
 int pg0=pg;
  double r;
  pg=(pg+1) % 7;
  r=a[pg];
  a[pg0] = r+(r-a[pg0])*6.0;
  n--;
 }
 return a[pg]+(double)m/3.5+c0;
}

71 ::2001/08/16(木) 11:46
何かネタない? age

72 :デフォルトの名無しさん:2001/08/19(日) 12:57
age

73 :デフォルトの名無しさん:2001/08/20(月) 10:41
メタボールと視線ベクトルとの交差判定の方法を知りたいんです。
たぶん3D系よりもこっちの方が向いてそうだと思うんですが。

74 :デフォルトの名無しさん:2001/08/20(月) 10:47
>>73 専門スレ以外で聞く時は専門用語の解説をしておくのがエチケットだよ

75 :デフォルトの名無しさん:2001/08/20(月) 10:49
>>73
そこまで行ったら数学板逝って訊いた方がいい。

76 :デフォルトの名無しさん:2001/08/20(月) 11:09
>>74 ごめんなさい。
http://www.kaigisho.ne.jp/literacy/midic/data/k34/k3434.htm
こういうヤツです。あのターミネーターでも使われてたヤツ。

>>75

できるだけ高速に、無駄なく、精度良く調べたいんです。
http://www.eml.hiroshima-u.ac.jp/member/jrs/nis/javaexampl/metaj/metajav.html

ニュートン法じゃダメですよね・・・

77 :デフォルトの名無しさん:2001/08/20(月) 11:16
>>76 それじゃまだ判らないよ

3次元上の点 Pn と その距離 Rn に応じた濃度 f(Rn)
Σ f(Rn) = C になる点の集合で表現するようだという事は判るけど

fはどんな関数? (1/Rn)^2 みたいな感じ?

78 :デフォルトの名無しさん:2001/08/20(月) 16:34
>>77 アウアウア- 説明下手でごめんなさい。


基本的には、f(Rn)=^{def}(1/Rn)^2で結構です。
それ以外にもいろいろ種類はあります(直方体とか)が、
まずはメタボール球を表示したいと思いまして。

アルゴリズムにはレイトレーシングを使ってます。

79 :デフォルトの名無しさん:2001/08/20(月) 16:51
各点ごとに 重みみたいなのが違うんですね?

Pn迄の距離 Rn から Σ (Wn/Rn^2) =1 になる点の集合って事ですね

ニュートン法でいいんじゃないでしょうか?

80 :◆3DelPhIM:2001/08/20(月) 20:15
結局、精度のよい初期値をどう求めるかという問題じゃないかな
先に荒く多面体近似してそれとの交点を求めてからニュートン法かな

81 :78:2001/08/20(月) 21:44
あと、問題としては法線ベクトルがあるんです。
法線をどうにか取得しなきゃいけないのです。


やっぱりニュートン法ですかね・・・

82 :78:2001/08/20(月) 22:16
http://www.ceres.dti.ne.jp/~dycoon/program/meta/emeta.html

自己レス。求めてた物は見つかりました。
でも法線がわっかんないんだよなぁ。

83 :デフォルトの名無しさん:2001/08/20(月) 22:42
78って・・・もしかして

84 :デフォルトの名無しさん:2001/08/20(月) 22:51
>>83
はっきり言え

85 :78:2001/08/21(火) 00:10
>>83
何ですか?

86 :78:2001/08/22(水) 00:02
>>83

なぁ。なんなんだよ。

87 :デフォルトの名無しさん:2001/08/22(水) 00:10
>>85-86
8分戻ってる!
とか一瞬思ってしまった。

88 :デフォルトの名無しさん:2001/08/22(水) 00:25
>>87 ありがとう(笑

89 :デフォルトの名無しさん:2001/08/22(水) 01:26
http://cheese.2ch.net/test/read.cgi?bbs=math&key=998375037&ls=50
見て

90 :デフォルトの名無しさん:2001/08/24(金) 23:25
Physics for Game Developers
http://www.oreilly.com/catalog/physicsgame/
10月に出版予定。

91 :デフォルトの名無しさん:2001/08/25(土) 05:42
#include<stdio.h>
int main(void)
{
char *s = "age";
printf("sage");

return 0;
}

92 :デフォルトの名無しさん:2001/08/25(土) 09:59
四則演算で7行かあ・・・
http://piza2.2ch.net/test/read.cgi?bbs=tech&key=994908590&st=551&to=551
これでも頑張ってる方だと思うからなあ

93 :デフォルトの名無しさん:01/09/25 22:01
お室こもひねの瑠璃の暦鼓膜誌筆祖トンはさきくかんまならむ゜まなゆやかおんえかうおやんゆなのよにわほにりのまくきはしちそしすかひきんくみなにのりらせれめろ゛瑠璃にね幕費は差費そしすかんまののれけりのまみきひしはしいすかになせるめむ゜理の門子祖は

94 :デフォルトの名無しさん:01/09/26 07:22
ここのスレッドに該当するかどうかは分かりませんが、質問します。
24時間制の"時刻"は、"秒"と"分"が60進数、"時"が24進数と分かっていて
「0時丁度から12345秒経過した時点での時・分・秒の値を求めよ」という問題も
簡単に解くことができます。求めるべき値が3個、○進数の要素が2つしかないからです。

これを一般化して"N個の数"があり、それぞれが独立して"○進数である"という
属性を持っているとき、前述の"12345"のように「ある値」を指示されたとき
N個の数におけるそれぞれの値を効率良く求める算法・アルゴリズムのようなものは
存在するのでしょうか? 勿論「ある値」は"N個の数"で表せる数値
(冒頭の時刻の例なら 24*60*60-1=86399)を超える値ではないものとします。

95 :デフォルトの名無しさん:01/09/26 07:49
>>94 n進数であるという事はあまり関係なく

x = Σ an*ΠAj ただしan<ΠAj に必ず解があるかという問題のような気がしますが?

96 :デフォルトの名無しさん:01/09/26 07:56
>>94
n桁目の値 = (ある値 / (nより小さい桁の進数の積)) % nの進数
// 桁ってのは24時間制なら 時=3桁目 分=2桁目 秒=1桁目 ってな感じね。

これじゃダメ?
効率が悪くてダメ?

>>95
意味わかんねえ…鬱。

97 :95:01/09/26 07:59
ごめん
ΠAj = A0*A1*A2・・・An という掛算のつもりです

98 :デフォルトの名無しさん:01/10/09 10:17
age

99 :デフォルトの名無しさん:01/10/21 20:35
AGE

100 :頭文字?:01/10/21 22:57
ところでこれって>>95 >>97
Σummation = 加算
Πroduct = 積
とかなの?
とかここで訊いちゃダメ?

101 :ヤパーリ:01/10/21 22:59
age

102 :1:01/10/24 08:05
N進数M桁の多倍長の計算方法

 負数 各桁毎に(N-1)の補数を取り、 キャリーcyを1にする
cy=1;
for(i=0;i<M;i++){
 cy = a[i]+(N-1-b[i])+cy;
  c[i]=cy % N;
  cy =cy / N;
}

103 :1:01/10/24 08:18
http://piza2.2ch.net/test/read.cgi?bbs=tech&key=1001998049&st=863&to=863&nofirst=true
あめ猫さんはちょっと間違ったみたい
0x10000 じゃなくて 0x10000-1 です

で補数を取った時の掛算のやり方
 1、 絶対値を求めてから掛算して 結果の符号によって再度負数にする方法
    桁数を可変にする多倍長の場合はこっちでやった方がいいかも

 2、そのまま掛算する場合は
    Bが負数の場合 Bを単純整数とみなすと B-N^Mになりますから
    A*(B-N^M)=A*B-A*N^M
   A,Bがともに負数の場合は
    (A-N^M)*(B-N^M)=A*B-(A+B)*N^M+N^M^2 ・・・・N^M^2 は桁外になるので

   結局 A,Bを符号無整数とみなして掛算して 負数なら M桁目から引けばよいという事になります

104 :1:01/10/24 08:52
10進数でやってみます。2桁としますが符号の為に3桁目を用意します

 23−49 の計算
最下位桁:CY=1; 3−9+CY = 3+10−1−9+CY=4
次の桁 :CY=0; 2−4+CY = 2+10−1−4+CY=7
最上位桁:CY=0: 0−0+CY = 0+10−1−0+CY=9

結果974となります。最上位の9は負数を示します
これをさらに符号を反転するには0から引算します。
最下位桁:CY=1; 0−4+CY = 0+10−1−4+CY=6
次の桁 :CY=0; 0−7+CY = 0+10−1−7+CY=2
最上位桁:CY=0: 0−9+CY = 0+10−1−9+CY=0

掛算のやりかた
掛算2桁X2桁で4桁になり、符号の為に5桁目を用意します
 −26*12=-312 の計算
まず負数を補数表現にして
 974*12=>74*12−7400=888-1200=−312

105 :デフォルトの名無しさん:01/10/25 01:04
アッカーマン関数っておもしろいですね。
普通は大学で習うのですか?

106 :デフォルトの名無しさん:01/10/25 01:13
>>102-104
解説ありがとうございます。
これをもとに実装できそうです。

もしよければ、除算の手がかりなんかも
アドバイスしてもらえないでしょか。

107 :1:01/10/25 08:42
多桁除算の方法は、
1)シフトしながら減算出来れば減算するという方法

2)ニュートン法>>9

があります。
 桁数が多く、掛算が高速に実装出来ているならニュートン法が良好です
 ニュートン法は初期値が悪いと収束迄時間がかかりますから、
 初期値は多桁の2数を浮動小数点化するか対数化して精度良く求めるのが
 後の計算回数を劇的に改善する事になります。

108 :デフォルトの名無しさん:01/10/25 09:45
FFTを使った高速な掛算はここでみかけたよ

   最速の素数判定アルゴリズム 
http://piza2.2ch.net/test/read.cgi/tech/993457354/

109 :Delあめ猫にゃ:01/10/25 10:01
>>103 フォローありがと

110 :106:01/10/25 17:42
>>107
ニュートン法は色々サンプルがあるようなので、2の方法で実装できそうです。

>>108
私もそこは読んでました。最終目標はそれなんですけど、
まずは動くものから作り上げないとしょうがないので、今は手を出せません。

111 :デフォルトの名無しさん:01/10/26 01:10
http://piza2.2ch.net/test/read.cgi/tech/1003559977/
x>yとして、荒い √(x*x+y*y) の計算でx+ (y*y/x)* 0.429で近似できるってのの
導出過程がちゃんと分かる方います?

(y/x)^2でテイラー展開すればそれっぽい形になるような気もするけど、
0.429がちょうどいいって所まではちょっと分からないです。

112 :1:01/10/26 07:47
>>111

√(x^2+y^2)=x*√{1+(y/x)^2}
√(1+a^2)を級数展開すると 1+a^2/4-a^4/8 + ・・・

だから 2項で止めると x+(y*y/x)*0.5

そこで、a0*x+a1*(y*y/x) として a0,a1が最適近似になるように調整したのでは


荒いhypotの計算方法はここに色々あるようです
ttp://www.infoeddy.ne.jp/~tensyo/prog/linealgo.htm#hypotenuse

精度の良い高速な計算方法はここ
http://www.sra.co.jp/people/miyata/algorithm/hypot.txt

113 :ななしヘタぐらま:01/10/26 14:06
>>61, >>63
化石レスですが
本双六=バックギャモンです.
確か奈良時か平安時代に日本に入ってきて,
江戸時代に現代の双六になった…んじゃなかったかな.

32 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)