求解思路：
对于carry状态，两串对应bit相加，结果为ONE+ONE=ZERO则标记GEN，为ONE标记PROP，ZERO+ZERO=ZERO标记为STOP
定义copy函数，使得用scani copy 操作上述所得串，GEN开始向右将非STOP标记的所有bit修改为ZERO，遇到STOP标记的ZERO停止，并将之改为ONE
对于GEN右侧所有的GEN标记过的bit进行加一操作
map转换至bit串
functor MkBigNumAdd(structure U : BIGNUM_UTIL) : BIGNUM_ADD = struct structure Util = U open Util open Seq (* Remove this line when you're done. *) exception NotYetImplemented infix 6 ++ datatype carry = GEN | PROP | STOP | None fun Copy (L,R) = case (L,R) of ((_,GEN),(_,STOP)) => (ONE,STOP) | ((_,GEN),(_,GEN)) => (ZERO,GEN) | ((_,STOP),(_,GEN)) => (ZERO,GEN) | ((_,PRO),(_,GEN)) => (ZERO,GEN) | ((_,GEN),(_,PROP)) => (ZERO,GEN) | ((_,PROP),(_,STOP)) => (ZERO,STOP) | ((ONE,STOP),(ONE,STOP)) => (ONE,PROP) | ((ONE,STOP),(ZERO,STOP)) => (ZERO,STOP) | ((ZERO,STOP),(ZERO,STOP)) => (ZERO,STOP) | ((ZERO,STOP),(ONE,STOP)) => (ONE,STOP) | ((_,PROP),(_,PROP)) => (ONE,PROP) | ((_,STOP),(_,PROP)) => (ONE,STOP) | ((_,None),(_,_)) => R fun Change ((nl,ll),(nr,lr)) = if lr = GEN then (if nl = ONE then (ZERO,lr) else (nr,PROP)) else (nl,ll) fun x ++ y = case (length x,length y) of (0,0) => empty () | (_,0) => x | (0,_) => y | (m,n) => let val (Left,Right) = if m>n then (x,y) else (y,x) val Temp = map (fn x => (ZERO,STOP)) Left val PreMask = map (fn x => if x=ONE then (ONE,GEN) else (ZERO,STOP)) Right val Mask = append (PreMask,subseq Temp (length Right,length Left - length Right)) val PreSeq = map (fn x => if x=ONE then (ONE,PROP) else (ZERO,STOP)) Left val ReSeq = map2 Change PreSeq Mask (*val SecMask = append (singleton (ZERO,STOP),ReSeq) val TrdMask = map2 (fn ((nl,ll),(nr,lr)) => if ll=GEN andalso lr=GEN then (ONE,GEN) else (ZERO,STOP)) ReSeq SecMask val ForMask = append (TrdMask , singleton (ZERO,STOP))*) val Result = scani Copy (ZERO,None) ReSeq val n = length Result val FivMask = map2 (fn ((nl,ll),(nr,lr)) => (nl,lr)) ReSeq Result val SixMask = append (singleton (ZERO,STOP),FivMask ) val SevMask = map2 (fn ((nl,ll),(nr,lr)) => if ((ll=lr)andalso(ll=GEN)) then (ONE,GEN) else (nl,ll)) ReSeq SixMask val EghMask = append (SevMask , singleton (ZERO,STOP)) val SecResult = if #1 (nth Result (n-1)) = ZERO then append (Result , singleton (ONE,STOP)) else Result val PreSult = map (fn (n,l) => n ) (map2 (fn ((nl,ll),(nr,lr)) => if (nr=ONE andalso lr=GEN) then (nr,lr) (*else if ll=PROP then (ZERO,GEN)*) else (nl,ll)) SecResult EghMask) in PreSult end val add = op++ end
求解思路：
计算机中，x的相反数-x为对x逐位取反后加一，后进行加法操作即可，注意舍去最后的符号位
functor MkBigNumSubtract(structure BNA : BIGNUM_ADD) : BIGNUM_SUBTRACT = struct structure Util = BNA.Util open Util open Seq
(* Remove this line when you're done. *) exception NotYetImplemented
infix 6 ++ --
fun x ++ y = BNA.add (x, y)
fun Reverse BigNum = let val Temp = map (fn x => if x=ONE then ZERO else ONE) BigNum val One = singleton ONE in Temp ++ One end
fun x -- y = case (length x,length y) of (0,0) => empty () | (_,0) => x | (0,_) => Reverse y | (m,n) => let val Temp = map (fn x => ZERO) x val Ty = append (y,subseq Temp (n,m-n)) in subseq (x ++ Reverse Ty) (0,m) end
val sub = op-- end
求解思路：
对于二进制数A、B
A*B = ( p*2^(m/2) +q )*( r*2^(n/2) + s ) = pr(2^n - 2^(n/2)) + (p +q)*(r +s)*2^(n/2) + (1-2^(n/2))*qs
从而分而治之
functor MkBigNumMultiply(structure BNA : BIGNUM_ADD structure BNS : BIGNUM_SUBTRACT sharing BNA.Util = BNS.Util) : BIGNUM_MULTIPLY = struct structure Util = BNA.Util open Primitives open Util open Seq
(* Remove this line when you're done. *) exception NotYetImplemented
infix 6 ++ -- infix 7 **
(* A*B = ( p*2^(m/2) +q )*( r*2^(n/2) + s ) = pr(2^n - 2^(n/2)) + (p +q)*(r +s)*2^(n/2) + (1-2^(n/2))*qs*) fun x ++ y = BNA.add (x, y) fun x -- y = BNS.sub (x, y) fun x ** y = case (length x,length y) of (0,_) => empty () | (_,0) => empty () | (1,1) => if (nth x 0) = ONE andalso (nth y 0) = ONE then singleton ONE else singleton ZERO | (m,n) => let val len = if m > n then m else n val mid = len div 2 val (q,p,s,r) = (subseq x (0,mid),subseq x (mid,m - mid),subseq y (0,mid),subseq y (mid,n - mid)) val (sum1,sum2) = (p ++ q,r ++ s) val (pr,qs,tp) = par3 (fn () => p ** r,fn () => q ** s,fn () => sum1 ** sum2 ) val Temp = tp -- pr -- qs val Q1 = append ((tabulate (fn i => ZERO) (mid*2)),pr) val Q2 = append ((tabulate (fn i => ZERO) mid),Temp) in Q1 ++ Q2 ++ qs end val mul = op** end
