[Haskell-beginners] Efficient Binary Multiplication

[Steven Leiva]

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


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