2の平方根

四角数は整数nの2乗です。
2の平方根は２００に一番近い四角数を探し、そのもととなったｎの桁をずらせば求まります。
Haskellで計算しますと

*Main> takeWhile (\(a,b) -> b < 200) $ map (\x -> (x , x*x)) [1..]
[(1,1),(2,4),(3,9),(4,16),(5,25),(6,36),(7,49),(8,64),(9,81),(10,100),(11,121),(12,144),(13,169),(14,196)]
*Main>

２００に一番近い四角数は１９６でｎは１４。
桁をずらして１．４。

これは2の平方根の近似値です。
偶然ですがとてもよい近似値です。

*Main> 1.4*1.4
1.9599999999999997
*Main>

さらに２００を百倍して２００００に一番近い四角数を探しますと

*Main> last $ takeWhile (\(a,b) -> b < 20000) $ map (\x -> (x , x*x)) [1..]
(141,19881)
*Main>

ともう一桁詳しい√２が求まります。

これを関数化しますと

*Main> let f k = last $ takeWhile (\(a,b) -> b < 2*100^k) $ map (\x -> (x , x*x)) [1..]
*Main> f 3
(1414,1999396)
*Main> f 4
(14142,199996164)
*Main> f 5
(141421,19999899241)
*Main>

ただしｋを大きくとると四角数のリストを作るのに負担が増えて現実的ではありません。

少し工夫を加えたのが折り紙をつかった計算法です。

正方形の折り紙を２枚用意します。
１枚を台紙に貼ります。
もう１枚を１００等分します。

小さな折り紙が１００枚できたことになります。

最初の折り紙の下辺、右辺に沿ってこの小さな折り紙を並べていきます。

下辺に１０枚、右辺に１０枚、角に１枚、合計２１枚並べることができました。
こうしてできた図形はやはり正方形です。

まだ小さな折り紙がのこっているので同様の作業を繰り返します。

こんどは下辺に１１枚、右辺に１１枚、角に１枚、合計２３枚並べることができました。

この作業は計４回繰り返すことができます。

この４回という数字を記録しておきます。
√２の一桁目の値です。

*Main> 21+23+25+27
96

１００−９６＝４

ですので小さな折り紙が４枚あまります。

その４枚の小さな折り紙をそれぞれ、再び１００等分します。

同様の作業をしますと
こんどは下辺に１４０枚、右辺に１４０枚、角に１枚、合計２８１枚並べることができました。
数がたりないので１回だけ並べることができます。

１を記録します。√２の次の桁の値です。

余った２１９枚をさらに百等分して・・・

とこの作業を無限に繰り返せば無限に詳しい２の平方根が求まります。
StateMonadを使ってアルゴリズムに忠実に書くとこうなります。

---

実行例

$ runghc root2.hs
(10,100,0,0,0,1)
(10,100,21,0,1,1)
(10,100,44,21,2,1)
(10,100,69,44,3,1)
(10,100,96,69,4,1)
(10,100,125,96,5,1)
4
(140,400,0,0,0,2)
(140,400,281,0,1,2)
(140,400,564,281,2,2)
1
(1410,11900,0,0,0,3)
(1410,11900,2821,0,1,3)
(1410,11900,5644,2821,2,3)
(1410,11900,8469,5644,3,3)
(1410,11900,11296,8469,4,3)
(1410,11900,14125,11296,5,3)
4
(14140,60400,0,0,0,4)
(14140,60400,28281,0,1,4)
(14140,60400,56564,28281,2,4)
(14140,60400,84849,56564,3,4)
2
(141420,383600,0,0,0,5)
(141420,383600,282841,0,1,5)
(141420,383600,565684,282841,2,5)
1
(1414210,10075900,0,0,0,6)
(1414210,10075900,2828421,0,1,6)
(1414210,10075900,5656844,2828421,2,6)
(1414210,10075900,8485269,5656844,3,6)
(1414210,10075900,11313696,8485269,4,6)
3
(14142130,159063100,0,0,0,7)
(14142130,159063100,28284261,0,1,7)
(14142130,159063100,56568524,28284261,2,7)
(14142130,159063100,84852789,56568524,3,7)
(14142130,159063100,113137056,84852789,4,7)
(14142130,159063100,141421325,113137056,5,7)
(14142130,159063100,169705596,141421325,6,7)
5
(141421350,1764177500,0,0,0,8)
(141421350,1764177500,282842701,0,1,8)
(141421350,1764177500,565685404,282842701,2,8)
(141421350,1764177500,848528109,565685404,3,8)
(141421350,1764177500,1131370816,848528109,4,8)
(141421350,1764177500,1414213525,1131370816,5,8)
(141421350,1764177500,1697056236,1414213525,6,8)
(141421350,1764177500,1979898949,1697056236,7,8)
6
(1414213560,6712126400,0,0,0,9)
(1414213560,6712126400,2828427121,0,1,9)
(1414213560,6712126400,5656854244,2828427121,2,9)
(1414213560,6712126400,8485281369,5656854244,3,9)
2
(14142135620,105527215600,0,0,0,10)
()

計算はこちらで見れます。

２の平方根だけではなく任意の整数Nの平方根を求めるHaskellのコードが

http://hhg2the-haskell.blogspot.jp/2017/10/blog-post_26.html

さらに折り紙ではなくサイコロを１０００等分して並べる方法でNの立方根も計算します。