是否存在允许并行加法的自然数的代数表示？

Question

自然数可以使用二进制表示形式在对数空间中表示(此处为little-endian):

-- The type of binary numbers; little-endian; O = Zero, I = One
data Bin = O Bin | I Bin | End

然后可以通过调用函数()次数来实现a和添加.这种实现的问题在于它本质上是顺序的.为了添加2个号码,呼叫按顺序链接.(例如使用进位)的其他实现遭受相同的问题.很容易看出,添加不能与该表示并行实现.是否使用代数数据类型表示自然数,它采用对数空间,并且可以并行添加？bsuccessorO(log(N))absucadd

插图代码:

-- The usual fold  
fold :: Bin -> (t -> t) -> (t -> t) -> t -> t
fold (O bin) zero one end = zero (fold bin zero one end)
fold (I bin) zero one end = one (fold bin zero one end)
fold E zero one end       = end

-- Successor of `Bin` - `O(log(N))`
suc :: Bin -> Bin
suc (O bin) = I bin
suc (I bin) = O (suc bin)
suc E       = E

-- Calls a function `a` times
times :: Bin -> (t -> t) -> t -> t
times a f x     = fold a zero one end f where 
    one bin fs  = fs (bin (fs . fs))
    zero bin fs = bin (fs . fs)
    end fs      = x

-- Adds 2 binary numbers
add :: Bin -> Bin -> Bin
add a b = (a `times` suc) b

-- 1001 + 1000 = 0101
main = print $ add (I (O (O (I E)))) (I (O (O (O E))))

Answer 1

有许多并行加法器架构。托马斯·沃克·林奇 (Thomas Walker Lynch) 1996 年在德克萨斯大学奥斯汀分校的硕士论文给出了精彩的评论。请参阅第 9.1 节，他总结了最坏情况下的路径长度。

Lynch和 Swartzlander 加法器 (L&S)的最坏情况路径长度为 2*ceil(log4(N))+2，其中 N 是位数。他们的论文《生成树进位先行加法器》中介绍了该架构。

您可以通过谷歌搜索“快速加法器”找到关于许多简单架构的精彩解释。