Author |
Topic: Numbers as Linked Lists (Read 702 times) |
|
Ding Dong
Guest
|
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?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
 |
Re: Numbers as Linked Lists
« Reply #1 on: Jun 8th, 2005, 4:00am » |
 Quote  Modify
|
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 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Numbers as Linked Lists
« Reply #2 on: Jun 8th, 2005, 5:26am » |
Quote Modify
|
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
|
|
IP Logged |
--SMQ
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove