計算機数学I (2019) 第5回：Horner法，数の10進・2進変換 のメモ

Hornor.sml

(**
 * Computer Mathematics 2019 / Lecture 5, Part 1: The Horner's rule
 * https://atelieraterui.page.link/NqaR
 *
 * 講義を読んで書いたコード断片。
 * - 整数の 10 <-> 2進数変換
 * - 実数の小数部の 10 -> 2進数変換
 *)

structure Main =
struct

fun unfold f e =
  case f e
    of NONE => []
     | SOME (x,e) => x::unfold f e

(* Hornor 法 *)
fun hornor a x = foldl (fn(ai,y)=> y * x + ai) 0 a

fun assert cond msg =
  if cond() then ()
  else raise Fail msg

(* 2進数 -> 10進数 *)
fun bin2dec m =
  hornor m 2

val () = assert (fn()=> bin2dec [1,0,1,1,0,1,1] = 91) "bin2dec"

(* 10進数 -> 2進数 *)
fun dec2bin m =
  rev (unfold (fn x=> if x = 0 then NONE else SOME(x mod 2, x div 2)) m)

val () = assert (fn()=> dec2bin 91 = [1,0,1,1,0,1,1]) "dec2bin"

(* 0 | 1 *)
structure Bin =
struct
  datatype t = B0 | B1
  fun toInt B0 = 0
    | toInt B1 = 1

  fun toChar B0 = #"0"
    | toChar B1 = #"1"
end

fun find p xs =
  let
    fun find' []      _ = NONE
      | find' (x::xs) i =
          if p x then SOME (i,x)
          else find' xs (i+1)
  in
    find' xs 0
  end

(* 小数部の二進数表記 *)
fun small_dec2bin numor denom =
  let
    val () =
      if numor >= denom then raise Domain else ()
    val cycle = ref NONE
    fun go n =
      unfold (fn (n,ss) =>
        if n = 0
        then NONE
        else
          let val n2 = n * 2 in
            case find (fn x=>x=n) (rev ss)
              of SOME (i,_) =>
                 (cycle := SOME i; NONE)
               | NONE =>
                 if n2 >= denom
                 then SOME(Bin.B1, (n2 - denom, n::ss))
                 else SOME(Bin.B0, (n2, n::ss))
          end)
        n
  in
    (go (numor, []), !cycle)
  end

fun s_to_string (xs,c) =
  let
    val xs = map Bin.toChar xs
  in
    case c
      of NONE => implode xs
       | SOME r =>
         (* 循環小数 *)
         let
           open List
           val former = implode (take (xs,r))
           val latter = implode (drop (xs,r))
         in
           String.concat [former, "(", latter, ")"]
         end
  end

local open Bin in 
val to_bin = small_dec2bin
val () = assert (fn()=> to_bin 0 10 = ([], NONE)) "0/10 is []"
val () = assert (fn()=> to_bin 0  8 = ([], NONE)) "0/8 is []"
val () = assert (fn()=> to_bin 1  8 = ([B0,B0,B1],NONE)) "1/8 to .001"
val () = assert (fn()=> to_bin 1 10 = ([B0,B0,B0,B1,B1],SOME 1)) "1/10 to .000110011.."
end

end