スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

[Ruby]数字の桁を漢字で表示するモジュールを作ったよ

最近アルゴリズムの本を勉強しつつブログに書いたりしているのですが、そのとき出力した結果がものすごい桁数の数字であることがあります。

まあ、こうやってブログに貼り付ける分にはそのままでもいいのですが、人に口頭で数字を伝えるときにいちいち桁を数えて読み上げるのは非常にめんどくさい。

そこで、FixnumとBignumを拡張するモジュール組んで読み込ませることで、整数を読み上げやすい形式に変換するプログラムを組んでみました。俺得。

# encoding: cp932
module Toj
  def to_j
    number = self
    digit = ["万", "億", "兆", "京", "垓", "禾予", "穣", "溝", "澗", "正",
             "載", "極", "恒河沙", "阿僧祇", "那由他", "不可思議", "無量大数"]
    ketasu = digit.size
    shuturyoku = Array.new
    ketasu.times do |i|
      numbers_stack = Array.new
      4.times do |j|
        stack = number - number / 10 * 10
        numbers_stack.unshift("#{stack}")
        number = number / 10
      end
      shuturyoku.unshift(numbers_stack.join.to_i.to_s)
      if number > 0
        shuturyoku.unshift(digit[i])
      else
        break
      end
    end
    puts shuturyoku.join
  end
end

class Fixnum
  include Toj
end

class Bignum
  include Toj
end

number = 95849480083929012345
number.to_j #=>9584京9480兆839億2901万2345

(自分だけかもしれないけど)便利!
スポンサーサイト

テーマ : プログラミング - ジャンル : コンピュータ

[Ruby][アルゴリズム入門]補間

第二章「数値計算」 目次

総合目次

2-1 乱数
2-2 数値積分
2-3 テイラー展開
2-4 非線形方程式の解法
2-5 補間
2-6 多桁計算
2-7 長いπ
2-8 連立方程式の解法
2-9 線形計画法
2-10 最小2乗法

ラグランジュ補間

何組かのx, yデータが与えられているとき、これらの点を通る補間多項式をラグランジュ補間により求め、データ点以外の点を求める。

(x0, y0), (x1, y1), …, (xn-1, yn-1)というn個の点が与えられたとき、これらの点を全て通る関数f(x)は次のように求められる。
ラグランジュ補間のf(x)を求める式
def lagrange(x, y, n, t)
  s = 0.0
  n.times do |i|
    p = y[i]
    n.times do |j|
      p = p * (t - x[j]) / (x[i] - x[j]) unless i == j
    end
    s = s + p
  end
  return s
end

x = [0.0, 1.0, 3.0, 6.0, 7.0]
y = [0.8, 3.1, 4.5, 3.9, 2.8]

puts "      x       y"
(0.0).step(7.0, 0.5) do |t|
  printf "%7.2f%7.2f\n"%[t, lagrange(x, y, 5, t)]
end


ニュートン補間

何組かのx, yデータが与えられているとき、これらの点を通る補間多項式をニュートン補間により求め、データ点以外の点を求める。

ニュートンの補間公式
fj(x)を,fj(xi)=yi,i=0,・・・,j
を満たす高々j次の多項式とすると,
fj+1(xi)=yi,i=0,・・・,j,j+1
を満たす高々j+1次の多項式fj+1(xi)は適当な定数cj+1に対して次の式で与えられる。

fj+1(x)=fj(x)+cj+1(x-x0)(x-x1)・・・(x-xj)

ニュートンの補間公式
def newton(x, y, n, t)
  flag = true
  a = Array.new(100) # 係数配列
  w = Array.new(100) # 作業用
  if flag
    n.times do |i|
      w[i] = y[i]
      (i - 1).downto(0) do |j|
        w[j] = (w[j + 1] - w[j]) / (x[i] - x[j])
      end
      a[i] = w[0]
    end
    flag = false
  end
  s = a[n - 1]
  (n - 2).downto(0) do |i|
    s = s * (t - x[i]) + a[i]
  end
  return s
end

x = [0.0, 1.0, 3.0, 6.0, 7.0]
y = [0.8, 3.1, 4.5, 3.9, 2.8]

puts "      x       y"
(0.0).step(7.0, 0.5) do |t|
  printf "%7.2f%7.2f\n"%[t, newton(x, y, 5, t)]
end

テーマ : プログラミング - ジャンル : コンピュータ

[Ruby][アルゴリズム入門]非線形方程式の解法

第二章「数値計算」 目次

総合目次

2-1 乱数
2-2 数値積分
2-3 テイラー展開
2-4 非線形方程式の解法
2-5 補間
2-6 多桁計算
2-7 長いπ
2-8 連立方程式の解法
2-9 線形計画法
2-10 最小2乗法

2分法

方程式f(x)=0の根を二分法により求める。

1次方程式(グラフ上で直線)以外の方程式を非線形方程式と呼ぶ。このような方程式の根(f(x)^2が最小値(=0)になるxの値)を求める方法に二分法がある。
1:根の左右にある2点a,bをlowとhighの初期値とする。
2:lowとhighの中間点xをx=(low + high) / 2で求める。
3:f(x) > 0なら根はxより左にあるからhigh = xとし、上限を半分に狭める。f(x) < 0なら根はxより右にあるからlow = xとし、下限を半分に狭める。
4:f(x)が0か|high - low| / |low| < EPSになったときのxの値を求める根とし、そうでないなら2以後を繰り返す。EPSは収束判定値で、適当な精度を選ぶ。
# encoding: cp932
def f(x)
  return x * x * x - x + 1
end

EPS = 1e-08  # 打ち切り誤差
LIMIT = 50   # 打ち切り回数

low = -2.0
high = 2.0

1.upto(LIMIT) do |k|
  x = (low + high) / 2
  if f(x) > 0
    high = x
  else
    low = x
  end

  if f(x) == 0 or (high - low).abs < low.abs * EPS
    puts "x = #{x}"
    break
  end
  if k == LIMIT
    puts "この試行回数、または誤差設定では収束しない"
  end
end


ニュートン法

方程式f(x)=0の根をニュートン法により求める。

1:根の近くの適当な値x0を初期値とする。
2:y = f(x)のx = x0における接戦を引き、x軸と交わったところをx1とし、以下同様の手順でx2, x3, …, xn-1, xnと求めて行く。
3:ニュートン法の収束判定になったときのxnの値を求める根とし、そうでないなら2以降を繰り返す。EPSは収束判定値で、適当な精度を選ぶ。

xnは、
ニュートン法のxnを求める式
と前の値xn-1を用いて求めることができる。ニュートン法の方が2分法より収束が早い。
# encoding: cp932
def f(x)
  return x * x * x - x + 1
end

def g(x)
  return 3 * x * x - 1
end

EPS = 1e-08  # 打ち切り誤差
LIMIT = 50   # 打ち切り回数

x = -2.0

1.upto(LIMIT) do |k|
  dx = x
  x = x - f(x) / g(x)
  if (x - dx).abs < dx.abs * EPS
    puts "x = #{x}"
    break
  end
  if k == LIMIT
    puts "この試行回数、または誤差設定では収束しない"
  end
end

テーマ : プログラミング - ジャンル : コンピュータ

[Ruby][アルゴリズム入門]テイラー展開

第二章「数値計算」 目次

総合目次

2-1 乱数
2-2 数値積分
2-3 テイラー展開
2-4 非線形方程式の解法
2-5 補間
2-6 多桁計算
2-7 長いπ
2-8 連立方程式の解法
2-9 線形計画法
2-10 最小2乗法

e^x

e^xをテイラー展開を用いて計算する。

# encoding: cp932
def myexp(x)
  eps = 1e-08;
  s = 1.0
  e = 1.0
  d = 1.0
  1.upto(200) do |i|
    d = s
    e = e * x / i
    s += e
    return s if (s - d).abs < eps * d.abs
  end
  return 0.0
end

puts "    x       myexp(x)        exp(x)"
0.step(40, 10) do |x|
  printf "%5.1f%14.6g%14.6g\n"%[x, myexp(x), Math.exp(x)]
end


負の値版e^x

e^xのxが負の場合にも対応できるようにする。

# encoding: cp932
def myexp(x)
  eps = 1e-08;
  s = 1.0
  e = 1.0
  d = 1.0
  a = x.abs # xの絶対値を取り、計算にはこれを使う
  1.upto(200) do |i|
    d = s
    e = e * a / i
    s += e
    if (s - d).abs < eps * d.abs
      # 元のxの値が0以上ならそのまま、0以下なら1/sを返す。
      if x > 0
        return s
      else
        return 1.0 / s
      end
    end
  end
  return 0.0
end

puts "    x       myexp(x)        exp(x)"
-40.step(40, 10) do |x|
  printf "%5.1f%14.6g%14.6g\n"%[x, myexp(x), Math.exp(x)]
end


cos x

cos xをテイラー展開により求める

# encoding: cp932
def mycos(x)
  eps = 1e-08
  s = e = d = 1.0
  # xの値を0~2πに収める
  x = x % (2 * 3.14159265358979)
  k = 1
  1.step(200, 2) do |k|
    d = s
    e = -e * x * x / (k * (k + 1))
    s += e
    return s if (s - d).abs < eps * d.abs
  end
  return 9999.0
end

rd = 3.14159 / 180
puts "    x       mycos(x)        cos(x)"
x = 0
0.step(180, 10) do |x|
  printf "%5.1f%14.6g%14.6g\n"%[x, mycos(x * rd), Math.cos(x * rd)]
  x += 10
end

テーマ : プログラミング - ジャンル : コンピュータ

[Ruby][アルゴリズム入門]数値積分

第二章「数値計算」 目次

総合目次

2-1 乱数
2-2 数値積分
2-3 テイラー展開
2-4 非線形方程式の解法
2-5 補間
2-6 多桁計算
2-7 長いπ
2-8 連立方程式の解法
2-9 線形計画法
2-10 最小2乗法

台形則による定積分

関数f(x)の定積分∫f(x)dxを台形則により求める。

# encoding: cp932

# 被積分関数
def func (x)
  return Math.sqrt(4- x * x)
end

print "積分区間 A?"
a = gets.chomp.to_i
print "積分区間 B?"
b = gets.chomp.to_i

N = 50.0
H = (b - a) / N
x = a
s = 0
1.upto(N - 1) do |i|
  x += H
  s += func(x)
end

sum = H * ((func(a) + func(b)) / 2 + s)
puts "  /#{b}"
puts "  |  sqrt(4-x^2) = #{sum}"
puts "  /#{a}"


シンプソン則による定積分

関数f(x)の定積分∫f(x)dxをシンプソン則により求める。

# encoding: cp932

# 被積分関数
def func (x)
  return Math.sqrt(4- x * x)
end

print "積分区間 A?"
a = gets.chomp.to_i
print "積分区間 B?"
b = gets.chomp.to_i

N = 50.0
H = (b - a) /(2 * N)
x = a
o = 0
e = 0
1.upto((N - 1) * 2) do |i|
  x += H
  if i % 2 == 0
    o += func(x)
  else
    e += func(x)
  end
end

sum = H * (func(a) + func(b) + 4 *(o + func(b - H)) + 2 * e) / 3
puts "  /#{b}"
puts "  |  sqrt(4-x^2) = #{sum}"
puts "  /#{a}"


テーマ : プログラミング - ジャンル : コンピュータ

[Ruby][アルゴリズム入門]乱数

第二章「数値計算」 目次

総合目次

2-1 乱数
2-2 数値積分
2-3 テイラー展開
2-4 非線形方程式の解法
2-5 補間
2-6 多桁計算
2-7 長いπ
2-8 連立方程式の解法
2-9 線形計画法
2-10 最小2乗法

一様乱数(線形合同法)

線形合同法を用いて、一様乱数を発生させる。

線形合同法は、適当なX0から初めて、
Xn=(Ax_(n-1) + C) % M
という式を使って、次々に0~Mの範囲の値を発生させる。

今回、A=109, C=1021, M=32768, X0=13を用いた。
$rndnum = 13 # X0の値

def irand
  $rndnum = ($rndnum * 109 + 1021) % 32768
  return $rndnum
end

100.times do |i|
  puts irand
end


一様性の検定

上記で作った乱数が、どのくらい均一にばらまかれているかをX^2(カイ2乗)検定の手法で計算する。

乱数が1~Mの範囲で発生するとき、iという値の発生回数をfi、iという値の発生期待値をFiとすると、
一様性の検定式
という値を計算する。このX^2の値が小さいほど均一にばらまかれていることを示す。
N = 1000
M = 10
F = N / M
SCALE = 40.0 / F

$rndnum = 13

def irnd
  $rndnum = ($rndnum * 109 + 1021) % 32768
  return $rndnum
end

def rnd
  return irnd / 32767.1
end

e = 0.0
hist = Array.new(M + 1, 0)
N.times do
  rank = (M * rnd).to_i + 1
  hist[rank] += 1
end

1.upto(M) do |i|
  printf "%3d:%3d"%[i, hist[i]]
  ((hist[i] * SCALE).to_i).times do |j|
    print "*"
  end
  puts

  e += (hist[i] - F) * (hist[i] - F) / F.to_f
end

puts " X2 = #{e}"


正規乱数(ボックス・ミュラー法)

正規乱数をボックス・ミュラー法により発生する。

def brnd (sig, m, rn)
  r1 = rand
  r2 = rand
  rn.x = sig * Math.sqrt(-2 * Math.log(r1)) * Math.cos(2 * 3.14159 * r2) + m
  rn.y = sig * Math.sqrt(-2 * Math.log(r1)) * Math.sin(2 * 3.14159 * r2) + m
end

st = Struct.new(:x, :y)
rn = st.new(0, 0)
hist = Array.new(100, 0)
1000.times do |i|
  brnd(2.5, 10.0, rn)
  hist[rn.x.to_i] += 1
  hist[rn.y.to_i] += 1
end

0.upto(20) do |i|
  printf "%3d : I "%[i]
  1.upto(hist[i] / 10) do |j|
    print "*"
  end
  puts
end

テーマ : プログラミング - ジャンル : コンピュータ

[Ruby]アルゴリズム入門をRubyで書いてみる・目次

第一章「ウォーミングアップ」 目次

1-0 アルゴリズムとは
1-1 漸化式
1-2 写像
1-3 順位付け
1-4 ランダムな順列
1-5 モンテカルロ法
1-6 ユークリッドの互除法
1-7 エラトステネスのふるい

第二章「数値計算」 目次

2-1 乱数
2-2 数値積分
2-3 テイラー展開
2-4 非線形方程式の解法
2-5 補間
2-6 多桁計算
2-7 長いπ
2-8 連立方程式の解法
2-9 線形計画法
2-10 最小2乗法

参考書籍

参考にした本はこちら。
C言語によるはじめてのアルゴリズム入門C言語によるはじめてのアルゴリズム入門
(1992/05)
河西 朝雄

商品詳細を見る

この本は三版まで出ています。今回参考にしたのは初版の方なので、目次や内容が違う可能性があります。
C言語によるはじめてのアルゴリズム入門 改訂第3版C言語によるはじめてのアルゴリズム入門 改訂第3版
(2008/10/02)
河西 朝雄

商品詳細を見る

テーマ : プログラミング - ジャンル : コンピュータ

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。