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...).
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
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@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
-- Steven Leiva 305.528.6038 leiva.steven@gmail.com http://www.linkedin.com/in/stevenleiva