multiplying large numbers uding linked lists

[anindyakar]

hello everyone,
I have to take a large number and put the individual digits along with their powers in different nodes of a linked list.Having done that how can I multiply,add,subtract and divide 2 such numbers kept in 2 linked lists.Please help [sig][/sig]

 

[ackka]

Hi, i am not sure i exactely understand your question, why you plan to seperate a large number into its seperate digits????? but to grab the data from two linked list is not to hard...
assuming your linked list looks like this..
//my syntax may be a little rusty
typedef struct whatever
{
int something;
whatever * next;
whatever * last;
};

make two linked lists
whatever * temp1, temp2;

for (;temp1->next == NULL || temp2->next == NULL; i++)
{
temp1->something = temp3;
temp2->something = temp4;
}

hope you get the picture, if not email me and i can send you some of my teachers notes.....

later B-)

[sig]<p>ackka<br><a href=mailto:tmoses@iname.com>tmoses@iname.com</a><br><a href=

http://home.cyberarmy.com/ackka>

my site</a><br>"Do No Harm, Leave No Tracks"<br>
ICMP Summer 2000, 2600 Article<br>
<br>
[/sig]

 

[shail]

hi anindyakar,

is it that u want the implementation in linked list readily given to u? it is available in gmp and many other such GNU multiprecision libraries.

If u want the idea behind it:

u have 32 bit no arithmetic normally. if u have a 33 bit no and want to say + , -, * or / with 1 say a no. 0x100000000 that is the question right??
many better methods may be possible but u can devise ur own by scaling down the problem.. take a 8 bit element as ur max available size and consider u want to do 0x100 +-*/ 0xnn... u will get it remembet consider that 0xnn is a 8 bit no. first... then breaking up will be easy.

hope this helps,

shail. [sig][/sig]

 

[anindyakar]

Dear accka,
Thank you for your reply.However,this is not what I had asked for.I know how to grab data from a linked list.The problem here is multiplication of 2 numbers in polynomial form,where x=10.For instance,you can express 539
as 5*10$2+3*10$1+9*10$0,(where $=power) which is a 2nd degree polynomial.I keep this polynomial in a linked list where each node has 3 fields
1.Coefficient(e.g. 5)
2.Exponent of 10(e.g 2)
3.a pointer
Having achieved this,I want to multiply 2 numbers such as 539 and 1457 which are kept in 2 separate linked lists,and obtain the result in another linked list.
I have completed the multiplication process but I am stuck with division.Also,I have to do this with decimal digits not hex,
Thank You [sig][/sig]

 

[Lim]

Like in first grade of Russian school:
2345677 / 334
(2<334) 0
(23<334) 00
(234<334) 000
(2345>334)
(2345/334=7)
334*7=2338 0007
2345-2338=7
7677
(76<334) 00070
(767>334)
(767/334=2)
334*2=668 000702
767-668=99
997
(997>334)
(997/334=2)
334*2=668 0007022
997-668=329
329
3290 0007022.
(3290>334)
(3290/334)=9
334*9=3006 0007022.9
3290-3006=284
2840
(2840<334)
(2840/334=8)
334*8=2671 0007022.98
2840-2671=169
1690
......... as long as you wish.
So:
2345677/334=7022.98 ......
This is an algorithm for recurcive function.The same algorithm works with binary (or hex) representation.

I don't think this is what you looking for and
I don't know how to separate 334. I just remeberd my first grade.
Regards.
[sig][/sig]

 

[rotovegasBoy]

just out of interest is this a out of interest thing or a need to multiply numbers out of the range of a long?

anyway if you just want to use big num,bers i thing gcc supports long long(s) we used them for a random number generator but i'm not sure if they're a gcc thing or a local addition.

if its the other i'd lookinto the way binary is implemented to perform the same operations. the methods should be the same just all the numbers will be powers of 10 rather than 2.

good luck [sig]<p>Chris Packham<br><a href=mailto:kriz@i4free.co.nz>kriz@i4free.co.nz</a><br><a href= > </a><br>A thousand mokeys at a thousand machines, it happened, it got called the internet.[/sig]

 

[rotovegasBoy]

whoops forgot to mention it might be easier to remember how to do the operations by hand (yes like back in school) [sig]<p>Chris Packham<br><a href=mailto:kriz@i4free.co.nz>kriz@i4free.co.nz</a><br><a href= > </a><br>A thousand mokeys at a thousand machines, it happened, it got called the internet.[/sig]

 

[ssingh]

The answer you will get in any good data structure and algorithm book as Multiplication of Polynomials using Linked list. Because it becomes a polynomial if you use integers bigger than the int data type's capacity.

Thanks
Siddhartha Singh [sig]<p>Siddhartha Singh<br><a href=mailto:siddhu_singh@hotmail.com>siddhu_singh@hotmail.com</a><br><a href=siddhu.freehosting.net> </a><br> [/sig]