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 |
Interesting question. So there is a concept in computer science called fusion.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:
-- _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners |
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.7401 On 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 |
In reply to this post by Quentin Liu
Hi Must you use only lists? Must each node only contain one digit? -- Sent from an expensive device which will be obsolete in a few months Casey On Sat, Apr 14, 2018, 1:30 PM Quentin Liu, <[hidden email]> wrote:
_______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners |
In reply to this post by Stephen Tetley-2
Thank you Stephen for the clarification! On Wed, Apr 18, 2018 at 12:33 PM, Stephen Tetley <[hidden email]> wrote: List fusion has existed for a long time (based on a change to the _______________________________________________ Beginners mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners |
Free forum by Nabble | Edit this page |