[Haskell-beginners] Efficient Binary Multiplication

Stephen Tetley stephen.tetley at gmail.com
Wed Apr 18 17:33:12 UTC 2018


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
>


More information about the Beginners mailing list