GIDForums  

Go Back   GIDForums > Computer Programming Forums > C++ Forum
User Name
Password
Register FAQ Members List Calendar Search Today's Posts Mark Forums Read

 
 
Thread Tools Search this Thread Rate Thread
  #1  
Old 04-Jul-2008, 22:56
Peter_APIIT Peter_APIIT is offline
Regular Member
 
Join Date: May 2007
Location: Malaysia
Posts: 545
Peter_APIIT can only hope to improve

Multiply Really Big Integer in Char *


Hello to all C== expect programmer, i want create a program which multiply two o char * integer.

I not asking you all to write for me but pointer and guide is really appreciated by me and others.

Thanks for your help.
  #2  
Old 06-Jul-2008, 07:50
Lancet Lancet is offline
New Member
 
Join Date: Jul 2008
Posts: 11
Lancet is on a distinguished road

Re: Multiply Really Big Integer in Char *


Do you mean, that your numbers are stored as text and you want to multiply those two strings?
If that is the case I would suggest searching for "c++ big int". There are tons of classes and functions out there that can parse strings and do arithmetics with that.
  #3  
Old 07-Jul-2008, 03:37
Peter_APIIT Peter_APIIT is offline
Regular Member
 
Join Date: May 2007
Location: Malaysia
Posts: 545
Peter_APIIT can only hope to improve

Re: Multiply Really Big Integer in Char *


Yes, absolutely right.

Thank for your suggestion.
  #4  
Old 07-Jul-2008, 22:01
Peter_APIIT Peter_APIIT is offline
Regular Member
 
Join Date: May 2007
Location: Malaysia
Posts: 545
Peter_APIIT can only hope to improve

Re: Multiply Really Big Integer in Char *


Before i started to post for help in this forums, i have think out of two algorithm by my own.

1. Multiply digit by digit.
2. Another algorithm is split the string number into two parts and multiply digit by digit also.

Therefore, karatsuba algorithm look similar to my second method. I decided to focus in it but carry number is the problem.

Besides that, i also not fully understand the whole algorithms. I just understand part of it from

Quote:
ozark.hendrix.edu

Explanation is greatly appreciated by me and others.

A billion thanks for your help.
  #5  
Old 08-Jul-2008, 03:46
Lancet Lancet is offline
New Member
 
Join Date: Jul 2008
Posts: 11
Lancet is on a distinguished road
Red face

Re: Multiply Really Big Integer in Char *


I am not sure if I understand that algorithm myself correctly but here are some more links that may help you:

http://en.wikipedia.org/wiki/Multiplication_algorithm
http://en.wikipedia.org/wiki/Karatsuba_algorithm

In the Kratsuba algorithm article in the "External Links" section you will find a link to this site:
http://utilitymill.com/utility/Karatsuba_Multiplication

There you can find this code (no clue what language that is but seems readable):
Code:
#import line added for compatibility with code execution change. #You can remove all but what is needed. import calendar,datetime,difflib,math,random,re,string,time,urllib max = 5 def split(l): if l % 2 == 0: return l / 2 else: return (l + 1) / 2 def max(a,b): if a > b: return a else: return b def mult(x,y): x = long(x) y = long(y) x_str = str(x) y_str = str(y) l1 = len(x_str) l2 = len(y_str) if (l1 < max and l2 < max): return x * y else: x_split = split(l1) y_split = split(l2) x1 = x[0,x_split] x2 = x[x_split + 1,l1 - 1] y1 = y[0,y_split] y2 = y[y_split + 1,l2 - 1] a = mult(x1,y1) b = mult(x2,y2) c = mult(x1 + x2,y1 + y2) m = max(l1,l2) d = (c - a - b) * 10**m e = b**(2 * m) z = a + d + e return z f = mult(x,y) print '''The product of''',x,'''and''',y,'''is''',f,'''.'''

The conversion to text seems to be missing here...

Do you have to write an algorithm by hand or would using something already written by someone else suffice (Homework/Just get the work done)?
  #6  
Old 08-Jul-2008, 20:53
Peter_APIIT Peter_APIIT is offline
Regular Member
 
Join Date: May 2007
Location: Malaysia
Posts: 545
Peter_APIIT can only hope to improve

Re: Multiply Really Big Integer in Char *


I prefer to learn Karatsuba algorithm with recursion.
Quote:

1. compute x1y1, call the result A
2. compute x2y2, call the result B
3. compute (x1 + x2)(y1 + y2), call the result C
4. compute C - A - B; this number is equal to x1y2 + x2y1.

number1 = 12, number2=12;

Result = C-A-B
=4 == X1y2 + x2y1=4;

Code:
BigInteger multiply(BigInteger a, BigInteger b) { int n = max(number of digits in a, number of digits in b) if(n == 1) { return a.intValue() * b.intValue(); } else { BigInteger aR = bottom n/2 digits of a; BigInteger aL = top remaining digits of a; BigInteger bR = bottom n/2 digits of b; BigInteger bL = top remaining digits of b; BigInteger x1 = Multiply(aL, bL); BigInteger x2 = Multiply(aR, bR); BigInteger x3 = Multiply(aL + bL, aR + bR); return x1 * pow(10, n) + (x3 - x1 - x2) * pow(10, n / 2) + x2; } }

I almost understand three multiply operation but doesn't the last statement and how to implement in recursion?

Explanation is greatly appreciated by me
Last edited by admin : 13-Jul-2008 at 01:19. Reason: Please insert your example codes between [CODE] and [/CODE] tags
  #7  
Old 09-Jul-2008, 01:12
Lancet Lancet is offline
New Member
 
Join Date: Jul 2008
Posts: 11
Lancet is on a distinguished road

Re: Multiply Really Big Integer in Char *


When the three multiplications are done the result can be computed by
Code:
x1 * pow(10, n) + (x3 - x1 - x2) * pow(10, n / 2) + x2;
x1*10^n + (x3-x1-x2)*10^(n/2) + x2

Of course each of the three multiplications will start a recursion.
Recursion will stop when one of the factors becomes a single digit number.
CPP / C++ / C Code:
int n = max(number of digits in a, number of digits in b)
if(n == 1) {
return a.intValue() * b.intValue();
} 

I guess you already found that out by your self...
So could you maybe phrase a little more precisely what part you don't understand?

EDIT 1: fixed punctuation
  #8  
Old 12-Jul-2008, 23:33
Peter_APIIT Peter_APIIT is offline
Regular Member
 
Join Date: May 2007
Location: Malaysia
Posts: 545
Peter_APIIT can only hope to improve

Re: Multiply Really Big Integer in Char *


1. I don't understand this statement.
CPP / C++ / C Code:
return x1 * pow(10, n) + (x3 - x1 - x2) * pow(10, n / 2) + x2;

2. How to implement recursion for Multiply() ?

Quote:

Recursion will stop when one of the factors becomes a single digit number.

The recursion is happen in multiply and not max.

Please help me.
  #9  
Old 13-Jul-2008, 03:34
Lancet Lancet is offline
New Member
 
Join Date: Jul 2008
Posts: 11
Lancet is on a distinguished road

Re: Multiply Really Big Integer in Char *


1. What makes you not understand the expression?
Is it the C++ or the algorithm?

2. The function does recurse by calling it self in it self:
CPP / C++ / C Code:
BigInteger x1 = Multiply(aL, bL);
These calls do the recursion.
  #10  
Old 13-Jul-2008, 03:36
Lancet Lancet is offline
New Member
 
Join Date: Jul 2008
Posts: 11
Lancet is on a distinguished road

Re: Multiply Really Big Integer in Char *


Wikipedia has a good article on recursion with examples. Maybe in your native language too
http://en.wikipedia.org/wiki/Recursion
 
 

Recent GIDBlogToyota - 2009 May Promotion by Nihal

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Pointer initialization causing program abend? emanresu C Programming Language 0 12-Dec-2006 11:36
lvalue compile error emanresu C Programming Language 7 16-Nov-2006 11:22
getting an error while compiling and running using different IDE. jaro C Programming Language 0 25-Aug-2006 10:14
Memory cannot be read? dlare9 C Programming Language 3 16-Nov-2005 08:03
[Tutorial] Pointers in C (Part I) Stack Overflow C Programming Language 1 08-Apr-2005 19:35

Network Sites: GIDNetwork · GIDWebHosts · GIDSearch · Learning Journal by J de Silva, The

All times are GMT -6. The time now is 01:25.


vBulletin, Copyright © 2000 - 2009, Jelsoft Enterprises Ltd.