Multiplication and division on integers split into parts

Does anyone know where I might get instructions on how to do multiplication and division (and maybe even modulus) on integers that are stored in parts? im making a library that stores a uint128_t as uint64_t UPPER, LOWER.

-------------Problems Reply------------

Are you familiar with GMP library? Why don't you use it instead of implementing your own?

  • The GNU Multiple Precision Arithmetic Library

From the above link, you can download tar.bz file for Unix-based OS.

For Windows, see this link:

  • GMP Install Instruction for Windows Platform

It has lots of information and installation file for MinGW, MSVC++, and CgyWin. Download that suits your need. You can also see these link:

  • How to Install and Run GMP on Windows Using MPIR
  • Building GMP library with Visual Studio? (Stackover topic)


After you're done with installation and configuration, you would like to know how to program using GMP, for that browse through these links:

  • GMP Basics
  • GMP Manual

Having your numbers splitted that way is an ideal prerequisite for Karatsuba multiplication. Consider:

x = x1 * 2^k + x2
y = y1 * 2^k + y2

Using the school multiplication, you would need 4 multiplications:

x*y = (x1*y1) * 2^(2*k) + (x1*y2 + x2*y1) * 2^k + x2*y2

Karatsuba needs a few more additions, but only 3 multiplications:

p1 = x1 * y1
p2 = x2 * y2
x*y = p1 * 2^(2*k) + ((x1+x2)*(y1+y2) - p1 - p2) * 2^k + p2

Of course the problem is how to deal with overflows.

http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic might be a good start. There are plenty of open source libraries already

Take a look at the various Big Integer libraries. Here's one that google found https://mattmccutchen.net/bigint/

I'm interested in the same subject, and I've found a similar question right here: How to implement big int in C++ I hope it will point you into the right direction!

Category:c# Views:1 Time:2011-05-25

Related post

  • Should I use multiplication or division? 2008-10-22

    Here's a silly fun question: Let's say we have to perform a simple operation where we need half of the value of a variable. There are typically two ways of doing this: y = x / 2.0; // or... y = x * 0.5; Assuming we're using the standard operators pro

  • Division between integers in Java 2011-03-05

    I need to perform division between integers in Java, and the result should be a float. Could I just use / symbol for it? As in: int integer1 = 1; int integer2 = 2; float quotient = integer1 / integer2; // Could I do this? --------------Solutions-----

  • How do I find the multiplication and division symbols on my Windows 7 calculator 2014-09-20

    How do I find the multiplication and division symbols on my Windows 7 calculator --------------Solutions------------- They are * for multiply and / for division. Sorry, but I do not understand your answer. I'm looking for the symbols, RE: X for multi

  • Multiplication of very long integers 2008-10-10

    Is there an algorithm for accurately multiplying two arbitrarily long integers together? The language I am working with is limited to 64-bit unsigned integer length (maximum integer size of 18446744073709551615). Realistically, I would like to be abl

  • MSVC generates strange/slow binary for some multiplications and divisions 2011-04-06

    I use MSVC 2010 SP1 and I have the following line of C++ code: int32_t c = (int64_t(a)*int64_t(b))>>2; When a and b are not constants, MSVC correctly generates a 32 bit imul and shrd instructions. But when a or b are constants it generates a ca

  • How do I implement multiplication and division in MIPS assembly without using the built in instructions? 2012-03-21

    Ok, here is the problem. I had to write a MIPS program that got 2 input numbers from the user. Then, I had to write a code that would output the product, quotient and remainder for the 2 numbers entered by the user. Now, that was pretty straight forw

  • polynomial evaluation accuracy, multiplication versus division 2009-11-17

    let us say I have have polynomial in x, divided by a power of x: p = (a + x(b + x(c + ..)))/(x**n) efficiency aside, which would be more accurate computation numerically, the above or using division: p = (((a/x + b)/x + c)/x + ...) thanks -----------

  • Fast multiplication of very large integers 2010-01-03

    How to multiply two very large numbers greater than 32 characters for example multiplication of 100! with 122! or 22^122 with 11^200 by the help of divide and conquer, do any body have java code or C# code? --------------Solutions------------- You sh

  • Splitting XML string with multiple XML documents using Java split() method 2011-08-17

    I am reading XML documents from a stream into a string. However, there is the possibility of multiple XML documents (identically structured) within the same string. I read several questions on stackoverflow and other sites which provided examples of

  • Multiple buttons on jquery mobile split button list? 2011-10-21

    Does anyone know how to add multiple buttons (2 split buttons) on a split button list? There is nothing mentioned in the documentation http://jquerymobile.com/test/docs/lists/lists-split.html Adding another <a> tag inside the listview doesn't c

  • Adding integers split into vectors 2012-01-31

    So, i'm trying to build a program that takes 2 integers. Later it splits the plus/minus sign and the digits and saves them into vectors. Last i would like to add those two integers. I managed to split the ints into the vectors and vector.size() gives

  • Junit - Multiple @Before vs. one @Before split up into methods 2012-02-03

    In a unit test, I need to perform a quite complex setup (this may be a code smell but this is not what this question is about :-)). What I'm interested in is if it is better to have multiple @Before methods performing the setup or just one, which cal

  • Compare multiplication and division 2012-04-16

    I want to know if there is any difference in speed between the following two methods #include<math.h> #include<iostream> using namespace std; int main() { float k=7; float b=4; cout<<(float)k/b<<" "<<endl; cout<<(f

  • Create multiple buttons with consecutive integers in name 2010-07-12

    I have the following python code and I was wondering if it's possible to create those buttons in a for loop instead? I was thinking of modifying the local namespace but I'm not sure if that's a good idea. I really want the buttons to be named so that

  • A simple addition,substraction,multiplication and division program 2011-04-13

    A simple C++ calculator program to calculate addition, subtraction, multiplication and addition... #include <iostream> #include <string> using namespace std; int main() { //input declarations as doubles for total and counter double total

  • Division of integers in Java 2011-08-28

    This is a ridiculous question but I can't find an answer. Have looked into floating point arithmetic and a few other topics but nothing has seemed to address this. I'm sure I just have the wrong terminology. Basically, I want to take two quantities -

  • Division of integers in a String 2011-09-13

    I have this string the first is the hours, second minutes, third seconds. 744:39:46 How do I divide the hours '744' in PHP? --------------Solutions------------- If I'm understanding you correctly, you want to get the substring '744' from the string '

  • More concise way to cast division of integers to decimal 2012-04-24

    I'm trying to divide some integers to get a percentage. By default I get an integer result, of course, so I cast to decimal. But I also would like the result to only have two places to the right of the decimal. --select (x - y) / y select (82 - 56) /

  • DV video import wizard with multiple file option does not split clips correctly 2014-03-26

    I am tyring to import my DV video using the wizard in Photo Gallery. If I import the entire tape, it works fine. However, when I chose the option to auto separate the video clips, the Wizard creates multiple files, but fails to trim the video at the

Copyright (C) dskims.com, All Rights Reserved.

processed in 0.089 (s). 11 q(s)