wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> cs >> Numbers as Linked Lists
(Message started by: Ding Dong on Jun 8th, 2005, 3:07am)

Title: Numbers as Linked Lists
Post by Ding Dong on Jun 8th, 2005, 3:07am
Hi,

I got this question in a Microsoft interview.

1) Design a struct to hold large integers(I suggested a linked list)

2) How will you efficiently perform operations + and * on two given large integers and store the result in the same struct.

Any solutions that you can think of?

Title: Re: Numbers as Linked Lists
Post by towr on Jun 8th, 2005, 4:00am
Multiplication is the trickiest bit.
You can do better than simple repeated addition, O(n^2). I think at least as well as O(n log(n))............. But I haven't the time to work it out now :P

Title: Re: Numbers as Linked Lists
Post by SMQ on Jun 8th, 2005, 5:26am
You can indeed do as well as O(n log(n)) using an FFT-style "butterfly" approach.  See, for example, the documentation for the Gnu Multi-Precision math library at http://www.swox.com/gmp/manual/Algorithms.html#Algorithms

--SMQ



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board