Fast way to Multiply two string numeric value

[Ramees219]

Happy new year ....

Hi i need to multiply two numeric string value i already created one but its not fast enough . I use same method when we doing in paper first i multiply all characters and saved in a vector and then later added all multiplyed output using string add function that i created . can't post that code becuse its big and not readable
I need a better multiply function how can i create one

And what is arbitrary precision i goto this website its good is this method faster than others

http://www.javascripter.net/math/cal...calculator.htm

[laserlight]

I suggest that you look into using an existing library like GMP, which has a C++ interface.

[Ramees219]

I suggest that you look into using an existing library like GMP, which has a C++ interface.

How can i use a external library i never used one and if included GMP how i use to multiply two strings ???

[laserlight]

How can i use a external library i never used one

That depends on your platform, compiler toolchain, and the library itself. It can be as simple as including a header file, though often it requires a little more, e.g., compiling one or more source files and/or linking to a library file.

and if included GMP how i use to multiply two strings ???

Read the documentation provided at the website that I linked to. You will not be multiplying two strings; you would be multiplying two numbers.

[2kaud]

'Big Integer' arithmetic is not usually done using a string to store the digits, as this method is slow - as you're found! If you have need for 'big integer' arithmetic then as laserlight suggested you should be looking at using an existing available library.

If this is just something you're developing for interest/learning then have a look at
http://stackoverflow.com/questions/4.../c-big-integer
http://stackoverflow.com/questions/2...t-big-int-in-c
http://www.codeproject.com/Articles/...-Integer-Class

I also produced a simple big int class. See this thread http://forums.codeguru.com/showthrea...ight=factorial

And what is arbitrary precision

See https://en.wikipedia.org/wiki/Arbitr...ion_arithmetic

[tiliavirga]

i need to multiply two numeric string value

The usual way is to convert the strings to a C++ fundamental type and then perform calculations on that type.

For example if you use long long int you can handle integers in the -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807 range.

If you instead use a double you get roughly the same precision but an even wider range ± 1.797,693,134,862,315,7 · 10^308.

If that's not enough I suggest you try to scale your problem before resorting to an arbitrary precision package. How much precision do you need really?

[Ramees219]

Maybe 7000 digit precision . If i am use any other arbitrary precision library how much time its going to take to multiply 7000 digit * 7000
On a single core i just want know a minimum time
And i just found that Schönhage-Strassen algorithm can multiplying very large integers in a reasonable amount of time.and also found code in this site but it's not running in my visual studio 2013 errors.....
http://googleweblight.com/?lite_url=...jg93mZgc79arYA

[2kaud]

The reason that the program doesn't compile with VS2013 is that it is trying to define the size of the array linearConvolution at runtime which is not allowed.

replace

    int linearConvolution[n + m - 1];
    for (int i = 0; i < (n + m - 1); i++)
        linearConvolution[i] = 0;

with

vector<int> linearConvolution(n + m - 1, 0);

and at the top of the program insert

#include <vector>

Note that this code only works for some input values. The given example produces the correct answer, but 34 * 56 doesn't - produces 904 instead of 1904; 5 * 7 produces 5. eg it sometimes leaves off the most significant digit in the answer. You'll need to debug the code to find the problem.

[Ramees219]

hi
i think fond a way to fix this problem . i don't know it already exists or not . i think its give 2000 digit value multiplication run fast
but i can't code this my own i am confused pls help me
my English is low i tried my best explain
multiplication.jpg

[laserlight]

Um, that looks like the beginning of an approach leading to the Karatsuba multiplication algorithm.

I suggest that you go back to trying to get a third party library to work for you, and see if it meets your needs. Implementing this yourself would be a good exercise, but if you are going to give up so easily with "but i can't code this my own i am confused pls help me", then there's no point.

[Ramees219]

i don't like to use library because i can't full understand it i need to do this way with maximum optimized for my problems
i am not give up on this i am full confided to code this but i am not sure it going to run maximum optimized i need an example by using
an a dynamic array .

my confusions

1, how to optimize this code to maximum speed
2, how to using dynamic array in this
3, how to get a range of 9 digit 9 digit value form dynamic array input to perform multiplication

[laserlight]

i don't like to use library because i can't full understand it i need to do this way with maximum optimized for my problems

If you cannot understand a library with available code that was written for your scenario and that was optimised by people who have been researching and experimenting with this much longer than you, then you have no hope at all of writing your own code such that it is "maximum optimized" for your problems.

1, how to optimize this code to maximum speed

You don't even have any code to speak of. You have an algorithm, but are you sure it is the most efficient algorithm? In the end, you may have to investigate and implement multiple algorithms to see which one is most efficient for your typical input.

2, how to using dynamic array in this

If you have to ask this: use a library.

3, how to get a range of 9 digit 9 digit value form dynamic array input to perform multiplication

If you have to ask this: use a library.

[Ramees219]

ok i will use a library i found this site

https://gist.github.com/evinugur/983e57f563f589699520

is this run fast or any other library how can i chose most optimized library

[Ramees219]

ok i am going to use this library FLINT: Fast Library for Number Theory
http://www.flintlib.org/features.html
thanks