# Efficient Binary Multiplication

5 messages
Open this post in threaded view
|

## Efficient Binary Multiplication

 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 [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Open this post in threaded view
|

## Re: Efficient Binary Multiplication

 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 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 [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners -- Steven Leiva305.528.6038[hidden email]http://www.linkedin.com/in/stevenleiva _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Open this post in threaded view
|

## Re: Efficient Binary Multiplication

 List fusion has existed for a long time (based on a change to the internal representation of lists to make them streams). IIRC the actual implementation was not considered a satisfactory replacement for GHCs existing list implementation as performance improvements were not uniform, the stream representation is good for some things worse for others. I don't know whether this situation has now changed. Byte String and Text exist because implementing strings or byte sequences as a cons list of Char or Byte is very inefficient both for storage / data locality and for many operations. Fusion for Byte String and Text is a bonus rather than a motivation. [*] Stream Fusion: From Lists to Streams to Nothing at All Duncan Coutts , Roman Leshchinskiy , Don Stewart http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.104.7401On 17 April 2018 at 01:48, Steven Leiva <[hidden email]> wrote: > 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 <[hidden email]> > 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 >> [hidden email] >> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners>> > > > > -- > Steven Leiva > 305.528.6038 > [hidden email] > http://www.linkedin.com/in/stevenleiva> > _______________________________________________ > Beginners mailing list > [hidden email] > http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners> _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners