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: https://hackage.haskell.org/package/bytestring-0.10.8.2/docs/Data-ByteString.html#t:ByteString).

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 binary?).

I hope this is useful.

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

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@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

Steven Leiva
305.528.6038
leiva.steven@gmail.com
http://www.linkedin.com/in/stevenleiva