algorithm - 是否有自然数的代数表示形式允许并行加法？

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

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

然后可以例如通过在a上调用b函数( successor )O(log(N))次来实现a和b的加法。这种实现方式的问题在于它本质上是顺序的。为了添加2个数字，suc调用按顺序链接。 add的其他实现(例如使用进位)也遇到相同的问题。很容易看出，添加不能与该表示并行执行。 是否有使用代数数据类型的自然数表示形式，需要对数空间，并且可以并行进行加法运算？

用于说明的代码:

-- 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))))

最佳答案

有许多并行加法器体系结构。 Thomas Walker Lynch's master's thesis at the university of Texas at Austin, 1996提供了一个很好的评论。请参阅第9.1节，其中总结了最坏情况下的路径长度。

Lynch和Swartzlander加法器(L＆S)在最坏情况下的路径长度为2 * ceil(log4(N))+ 2，其中N是该位数。该体系结构在他们的论文A Spanning Tree Carry Lookahead Adder中介绍。

通过搜索“快速加法器”，您可以找到有关许多简单体系结构的出色解释。

关于algorithm - 是否有自然数的代数表示形式允许并行加法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33722100/