Efficient Binary Multiplication

Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Efficient Binary Multiplication

Quentin Liu
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
Reply | Threaded
Open this post in threaded view
|

Re: 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 <[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




--

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Efficient Binary Multiplication

Stephen Tetley-2
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
KC
Reply | Threaded
Open this post in threaded view
|

Re: Efficient Binary Multiplication

KC
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:
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

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners