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