Hatena::Grouprubyist

たばさの RSSフィード

12/09(金) 2016

平方根 その3

平方根 その3 - たばさの を含むブックマーク はてなブックマーク - 平方根 その3 - たばさの

そしてニュートン法。

bigdecimalでも使っているようです。

しかし終了時間が予測できないし、続きを計算という手段がないので自前で作ります。

というより、bigdecimalというのがあったんだぁ、と後で気づくわけですが。


参考に収束する様子のグラフを探す。

> http://s-taichan.blogspot.jp/2012/02/sicp17.html

適当なxの値とその時点の接線から徐々に真の値に近づけていく感じ。ほんとに近づくのかとか、収束の速さはとか、思ったら結構速い。さすがニュートン。

#!/usr/bin/ruby
# -*- coding: utf-8 -*-

require 'optparse'

max=5
check=false
opt = OptionParser.new
opt.on('-a v',"loop max") {|v| max=v.to_i }
opt.on('-c',"check") {|v| check=v }
opt.parse!(ARGV)

def sqrtN x
  s=x.to_s.size-1
  d=("1"+"0"*(s*2)).to_i
  y=x*x-2*d
  a=2*x
  b=-(a*x-y)
  x=-b*d/a
end

st=Time.now
r=sqrtN(141421)
lim=6
max.times{|i|
  r=sqrtN(r)
  lim*=2
  r=r.to_s[0,lim].to_i
  STDERR.print","
  if check
    (r**2).to_s=~/^(20*|19*)/
    et=Time.now
    STDERR.puts "#{format"%.2f",et-st},#{$&.size}" if $&
  else
    et=Time.now
    STDERR.puts "#{format("%.2f",et-st)} #{i}"
  end
  print i,": "
  puts r
}

説明書こうかと思ったけど面倒なのでやめておくすまん。ルート2限定でとりあえず。前回と違い、検算しないと何桁まであっているか分からない状態。桁が増えると検算がまた大変。

実際に動かすと割と収束が速いなという印象だけども、印象だとか適当なこと言っているとまじめにやっている人には怒られてしまうのだ。たぶん。


そして、どうやら数値から文字列への変換がコストが高いよう。高速化を検索して見つかったので使ってみるも速くはならない、すでにruby本体に取り込まれている感触。感触?


有効桁数を考えなければ、1ステップごとに桁が倍々になる感じなので、そのへんが前回のbigdecimalでやった時の癖に関わるのかなという印象。

トラックバック - http://rubyist.g.hatena.ne.jp/hatecha/20161209

12/08(木) 2016

ランダムっぽい数列

ランダムっぽい数列 - たばさの を含むブックマーク はてなブックマーク - ランダムっぽい数列 - たばさの

息抜きに、2の平方根を2万桁ほど求めたところで、

ans.scan(/[12345]+/).sort_by{|i|i.size}

などとやって1から5までの数字だけから構成されるランダムっぽい長めの数列を探してみます

[:pos, 10780, :val, "1221413242532", :size, 13]

[:pos, 10293, :val, "134142214511", :size, 12]

[:pos, 19875, :val, "245352422314", :size, 12]

[:pos, 5217, :val, "45444122255", :size, 11]

[:pos, 8959, :val, "41123515355", :size, 11]

[:pos, 2024, :val, "45512331421", :size, 11]

[:pos, 5631, :val, "3152512411", :size, 10]

[:pos, 11596, :val, "1245211244", :size, 10]

[:pos, 11679, :val, "352454514", :size, 9]

[:pos, 5316, :val, "454512424", :size, 9]

まあそこそこいいんじゃないでしょうか。(なにが?)

下のほうにはランダムっぽくないのもありますね。

一応、ネットで検索して意味ありげな結果があるか確かめておきましょう。

トラックバック - http://rubyist.g.hatena.ne.jp/hatecha/20161208

12/06(火) 2016

平方根 その一

平方根 その一 - たばさの を含むブックマーク はてなブックマーク - 平方根 その一 - たばさの

それ何々でできるおっていうのはちょっと黙ってて。

まずとりあえず計算してみよう。


irb(main):001:0> 2**0.5

=> 1.4142135623730951

irb(main):002:0>

ソウジャナイ。。。



require 'optparse'

figure=2
opt = OptionParser.new
opt.on('-n num',"num") {|v| figure=v.to_i}
opt.parse!(ARGV)
exit if figure>9


def nextt n, v
  num=v-1
  t=n*10
  r=0
  if ((t+5)**2).to_s[0,1].to_i==num
    r=5
  end
  st=r
  10.times{|i|
    break if ((t+st+i)**2).to_s[0,1].to_i>num
    r=st+i
  }
  t+r
end

each=1000
a=(figure**0.5).to_i
st=Time.now
keta=0
while 1
  n=nextt(a,figure)
  et=Time.now
  keta+=1
  a=n
  if keta%each==0
    print keta
    tc=format(" %.2f: ",et-st)
    print tc,a," /\n"
    STDERR.print",",tc
  end
end

平方根 その2

平方根 その2 - たばさの を含むブックマーク はてなブックマーク - 平方根 その2 - たばさの

まあbigdecimalっていうのがあるらしいんですよ。sqrtも桁指定でだいたい。

irb(main):002:0> require 'bigdecimal'

=> true

irb(main):005:0> a=BigDecimal::new(2)

=> #<BigDecimal:2b85f10,'0.2E1',9(27)>

irb(main):008:0> puts a.sqrt(10)

0.1414213562373095048333333334E1

=> nil

いじっていると、計算時間になんだか癖がある。

キャッシュ?

1000>0.02sec

1500>2.5

2000>0.09~0.15

3000>19.5

4000>42~56

5000>0.045

6000>187.62

7000>279.43

8000>355.2

9000>534.8

10000>0.16

20000>0.63

40000>2.52

60000>over10hours

というわけでもなく、

得意な桁とそうでもない桁が。9000苦手なら10000出してしまえばいい、というのは結果がわかっているから言えることで。

ソース見ないとわからない。見れば分かるかはまた別の話。

トラックバック - http://rubyist.g.hatena.ne.jp/hatecha/20161206
カレンダー
<< 2017/03 >>
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
archive Error : RSSが取得できませんでした。