ruby-list

原です。


> けいじゅ＠SHLジャパンです. 

> うーん. アルゴリズムが良く分かりませんがこっちの方が良さそうな気もしま
> すね. これって, Bignumにも適応できますかね?? つまり, 数の範囲の制限を
> なくせます??

出沢さんもおっしゃっているように、最初は初期値を決めているだけです。
割り算を３回の所を２回にするには？とかいうオタクな世界なので、分か
りづらくなってます。数の範囲の制限は初期値のみ２べきを掛けてこのレ
ンジに納め、元に戻した後、ニュートン近似をとればそこそこいくと思い
ます。


> あと, 任意の数になると繰り返しが発生することになると思いますが, その回
> 数は見積もれるのでしょうか??

できると思いますが、ちゃんと考えたこと無かった。(^^;


> 開平法ですと処理時間オーダは, O(log n) となるので, それより良くなるの
> であればニュートン法を利用した方がよいですね.

ニュートン法でも log n ですね。同じ log n でもスピードが百倍違う場
合もあるので、このあたりなかなか難しいです。


後、出沢さんも気にしてますけど、これは整数演算なのでちょっと微妙な
ところがあります。つまり整数 d の整数の平方根 r を求める Newton 近似
の式は、[] をガウス記号( = Floor) として、

N(x) = [(x+[d/x])/2]

なんですね。だから実数の話とちがって、収束とか N(x) >= r でさえ、直に
はわかりません。結論をいうと N(x) >= r はどんな x に対しても正しく、
r+1 より大きい値に対して x, N(x), N(N(x)),.. は単調減少で、ほぼ倍々精
度になり、１つの例外を除いて r に収束します。その例外とは、

d が「平方数−１」の時、その時に限り r と r+1 で振動する。

というものです。


任意の大きさの整数について、N(x) の回数を見積もれるかどうかちょっと
考えてみます。


　　                         Shin-ichro Hara(Nagaoka Univ.of Tech.)

Thread

Prev Next

In This Thread

Prev Next

[#1152] Linux and ext/dbm.c — OZAWA Sakuro <crouton@...>

[#1153] Re: Japanese and tr — Shin-ichiro Hara <sinara@...>

[#1165] dynamic link [HP] — Yasuo OHBA <jammy@...>

[#1167] mistakes in Users' Guide(Oct 23) — Noritugu Nakamura <nnakamur@...>

[#1169] string literal new format — matz@... (Yukihiro Matsumoto)

[#1171] Re: string literal new format — Shin-ichiro Hara <sinara@...>

[#1174] Rational and Complex — keiju@... (Keiju ISHITSUKA)

[#1186] Re: ruby 0.99.3-961203 available — Shin-ichiro Hara <sinara@...>

[#1194] ruby-mode — Yasuo OHBA <jammy@...>

[#1196] ruby 0.99.3-961204 — matz@... (Yukihiro Matsumoto)

[#1208] Re: ruby 0.99.3-961204 — Shin-ichiro Hara <sinara@...>

[#1209] [Q] Scope of local variable — Shin-ichiro Hara <sinara@...>

[#1219] ruby animal — OZAWA Sakuro <crouton@...>

[#1231] Re: [BUG} delete (Re: ruby 0.99.3-961204) — Shin-ichiro Hara <sinara@...>

[#1243] Re: ruby 0.99.3-961204 — Shin-ichiro Hara <sinara@...>

[#1244] ruby 0.99.3-961210 available — matz@... (Yukihiro Matsumoto)

[#1248] ruby NutShell book — Kimijima Hideyuki <sanjigen@...>

[#1252] [Q] Escape of meta-char(Re: ruby 0.99.3-961210 available) — Shin-ichiro Hara <sinara@...>

[#1256] ruby 0.99.4-961212 available — matz@... (Yukihiro Matsumoto)

[#1270] thread and $1 — keiju@... (Keiju ISHITSUKA)

[#1280] Request for inspect — keiju@... (Keiju ISHITSUKA)

[#1285] (no subject in original) —

[#1288] None — (Dezawa Shin-ichiro) <dezawa@...>

[#1290] ruby 0.99.4-961217 will be available — matz@... (Yukihiro Matsumoto)

[#1293] MIX Offline Meeting — Shin-ichiro Hara <sinara@...>

[#1297] Re: MIX Offline Meeting — Shin-ichiro Hara <sinara@...>

[#1312] djgpp v2 and fpu — Noritugu Nakamura <nnakamur@...>

[#1313] Re: Rational and Complex — Shin-ichiro Hara <sinara@...>

[#1316] method nothing — keiju@... (Keiju ISHITSUKA)

[#1330] Re: Rational and Complex — Shin-ichiro Hara <sinara@...>

[#1361] [Dist] distributed ruby — keiju@... (Keiju ISHITSUKA)

[#1368] 代入の値 — (Dezawa Shin-ichiro) <dezawa@...>

[#1377] lock, unlock — WATANABE Hirofumi <watanabe@...>

[#1386] ruby 0.99.4-961219 available — matz@... (Yukihiro Matsumoto)

[#1393] new の override — (Dezawa Shin-ichiro) <dezawa@...>

[#1394] 同じメソッドで、引数が違う やつ — (Dezawa Shin-ichiro) <dezawa@...>

[#1395] None — (Dezawa Shin-ichiro) <dezawa@...>

[#1399] Ruby Glossary — matz@... (Yukihiro Matsumoto)

[#1404] Re: new の override — Sinichiro Dezawa <dezawa@...>

[#1418] Re: Ruby Glossary — Shin-ichiro Hara <sinara@...>

[#1420] Can't run Ruby (DJGPP) on PC-DOS — s.suda@...

[#1423] 配列への grep — (Dezawa Shin-ichiro) <dezawa@...>

[#1424] String.succ — (Dezawa Shin-ichiro) <dezawa@...>

[#1439] Re: Ruby Glossary — Shin-ichiro Hara <sinara@...>

[#1440] Re: Ruby Glossary — Shin-ichiro Hara <sinara@...>

[#1443] Ruby/AIX — s.suda@...

[#1449] diff -c C++ ruby — Sinichiro Dezawa <dezawa@...>

[#1453] About Win32 & DJGPP Package — Shin-ichiro Hara <sinara@...>

[#1454] Re: サブクラスの作成 再び — Shin-ichiro Hara <sinara@...>

[#1460] ruby 0.99.4-961224 available — matz@... (Yukihiro Matsumoto)

[#1462] wait child process — Itsuro Saito <saito@...>

[#1464] Re: wait child process — Shin-ichiro Hara <sinara@...>

[#1469] wish ... — Noritugu Nakamura <nnakamur@...>

[#1474] Ruby for AIX! — LH5S-SD@...

[#1481] 例外 — Sinichiro Dezawa <dezawa@...>

[#1484] Re: [ruby-list:1481] 例外 — Shin-ichiro Hara <sinara@...>

[#1486] Ruby.exe Error? — s.suda@...

[#1488] ruby 1.0 released finally!! — matz@... (Yukihiro Matsumoto)

[#1492] Re: Ruby.exe Error? —

[#1500] matz's vacation — matz@... (Yukihiro Matsumoto)

[#1505] djgpp ruby 1.0 —

[#1508] 型変換 — (Dezawa Shin-ichiro) <dezawa@...>

[#1509] C++ユーザのための手引 (Ver. 0.1.1) — (Dezawa Shin-ichiro) <dezawa@...>

[#1510] Congraturation! (Re:ruby 1.0 released finally!!) — Shin-ichiro Hara <sinara@...>

[#1511] Congratulation!!(Re: Congraturation!) — Shin-ichiro Hara <sinara@...>

[#1512] Re: ruby 1.0 on IRIX (Re: wish ...) —

[#1517] [Ruby/Tk] place ? — Noritugu Nakamura <nnakamur@...>

[#1518] dynamic endian check for nextstep — matz@... (Yukihiro Matsumoto)

[#1519] Re: ruby 1.0 on IRIX (Re: wish ...) —

[#1523] konnnichiha — Shirakata Takashi <sirakata@...>

[#1530] Hash の 加算 — (Dezawa Shin-ichiro) <dezawa@...>

[#1531] new — "Furutani Shun-ichi" <sf@...>

[#1532] Re: 例外 — Shin-ichiro Hara <sinara@...>

[#1533] Re: C++ ユーザのための手引 (Ver. 0.1.1) — Shin-ichiro Hara <sinara@...>

[#1537] Re: C++ ユーザのための手引 (Ver. 0.1.1) — Shin-ichiro Hara <sinara@...>

[#1547] Re: rbdj1227.lzh (ruby 1.0) —

[#1554] Re: rbdj1227.lzh (ruby 1.0) — Shin-ichiro Hara <sinara@...>

[ruby-list:1330] Re: Rational and Complex

Thread

In This Thread

[#1394] 同じメソッドで、引数が違うやつ — (Dezawa Shin-ichiro) <dezawa@...>

[#1454] Re: サブクラスの作成再び — Shin-ichiro Hara <sinara@...>

[#1530] Hash の加算 — (Dezawa Shin-ichiro) <dezawa@...>