Namaran

Code daily. Without assist.

2026-08-29

FibPower.hs

type M = (Integer, Integer, Integer, Integer)

mul :: M -> M -> M
mul (a, b, c, d) (e, f, g, h) = (a * e + b * g, a * f + b * h, c * e + d * g, c * f + d * h)

power :: M -> Int -> M
power m 0 = m
power m n
  | even n = let h = power m (n `div` 2) in mul h h
  | otherwise = mul m (power m (n - 1))

fib :: Int -> Integer
fib n = let (_, x, _, _) = power (1, 1, 1, 0) n in x

main :: IO ()
main = print (map fib [0 .. 5])

2行2列の行列を4つ組 (a, b, c, d)(1行目が a b、2行目が c d)で表し、(1, 1, 1, 0) の n 乗の右上の成分から、第 n 項のフィボナッチ数を求める fib です。フィボナッチ数は 0, 1 から始まり、前の2項の和を並べた数列です。map fib [0 .. 5] は本来 [0,1,1,2,3,5] になるはずが、いまは [1,1,3,5,21,34] になります。

Answer

Wrong

power m 0 = m

0乗は、何に掛けても相手を変えない行列 (1, 0, 0, 1) でなければなりませんが、ここでは m を返しています。そのため power m n は m の n 乗に余分な m を掛けた行列を返し、余分な m の個数は n によって変わります。power m 1 は mul m (power m 0) で2乗になり、power m 2 はそれを2乗するので4乗、power m 3 は5乗、power m 4 は8乗、power m 5 は9乗です。

(1, 1, 1, 0) の e 乗の右上はフィボナッチ数の第 e 項なので、n が0から5のときに読まれるのは第1、2、4、5、8、9項の 1, 1, 3, 5, 21, 34 です。1つ先へずれただけなら [1,1,2,3,5,8] になるはずのところ、2乗する枝が余分な m まで2乗するので、ずれは n が大きいほど広がります。

Right

power _ 0 = (1, 0, 0, 1)

(1, 0, 0, 1) は mul で何に掛けても相手をそのまま返すので、0乗をこれにすると、power m n は2乗の枝でも1つ掛ける枝でも、ちょうど m の n 乗になります。0乗の右上は0で、fib 0 も正しく0になります。0乗が引数の行列を使わなくなったので、引数は _ にしてあります1。

  1. m のまま残すと、使わない変数として -Wall が警告を出します。