[Haskell-beginners] Efficient Binary Multiplication

[Steven Leiva]

Thank you Stephen for the clarification!

On Wed, Apr 18, 2018 at 12:33 PM, Stephen Tetley <stephen.tetley at gmail.com>
wrote:

> 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 <leiva.steven at gmail.com> 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 <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
> >
> > _______________________________________________
> > Beginners mailing list
> > Beginners at haskell.org
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
> >
> _______________________________________________
> 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/20180428/f5ecf601/attachment.html>