[Haskell-beginners] Efficient Binary Multiplication

Steven Leiva leiva.steven at gmail.com
Tue Apr 17 00:48:40 UTC 2018

Interesting question.

So there is a concept in computer science called *fusion*.

My understanding (I don't have a CS degree) is that when data is subject to
fusion, we don't create the intermediary lists as you are talking about.
This is why, in Haskell, we have the *ByteString* and *Text* datatypes.
Unlike *String*, they (ByteString / Text) are subject to fusion. *Text* is
useful when we are dealing with unicode data, while *ByteString* is the
correct tool when we are dealing with binary data.

All of this is to say that you should look at the *ByteString* data type.
(Take a look at this description, for example:

The only potential problem I see is that *ByteString* internally uses
*Word8*, and since *Word8* is *unsigned*, negatives are problematic. (Now
that I think about it, how the heck do you represent negative numbers in

I hope this is useful.

On Sat, Apr 14, 2018 at 4:28 PM, Quentin Liu <quentin.liu.0415 at gmail.com>

> Hi all,
> Suppose I want to multiply two binary numbers whose representation uses
> lists (e.g. 14 is represented as [1, 1, 1, 0]). Is there any efficient way
> to do binary multiplication? The way I could come up with involves a lot of
> intermediate lists that will be discarded eventually and is extremely
> inefficient. I know one fast algorithm that uses Array but would it be
> possible to do the multiplication with only lists?
> Regards,
> Qingbo Liu
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

Steven Leiva
leiva.steven at gmail.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20180416/79305639/attachment.html>

More information about the Beginners mailing list