Gauging the scale of impact on large prime factorization

[TakenItSeriously]

I'm trying to get a feel for the scale of negative impact that the division operation involved in the factorization of large primes has on computational time.

 

Hypothetically speaking, if you could replace all division operations on large numbers with a multiplication operation on the same numbers instead, while assuming it achieved the same goals of course. What factor increase in efficiency do you think we would gain?

[fiveworlds]

Hypothetically speaking, if you could replace all division operations on large numbers with a multiplication operation on the same numbers instead, while assuming it achieved the same goals of course. What factor increase in efficiency do you think we would gain?

 

None the fastest way is called the Sieve of Eratosthenes it involves using an array. It still involves trial division but less off it. First you add two to an array. Then you work through your array testing divisibility. If you get to the end of your array then the number is prime and is pushed to the end of the array. This is a parralelisable operation for instance you can test for the divisibility of all numbers in an array up to the computer resources you have available and then the runtime becomes a polynomial multiple of the resources you have. There is the problem that after a certain point the primes take too much hard drive space so the Sieve of Eratosthenes won't work anymore and you are back to using trial division. The Sieve of Eratosthenes can be used to show that Primes are in P on a turing machine (theoretical computer with infinite resources) P=NP but most computers don't have infinite resources. If you just use multiplication the range of numbers you can possibly calculate on a normal computer decreases by a lot because you are even more limited by hard drive space. There is also a limit on using trial division which is basically if something takes longer than 20 years to calculate your computer will break. There is also the idea that today's limitations may not be limitations in the future new methods of data storage could become available which make just using the sieve the more viable option.

Edited May 26, 2017 by fiveworlds

[imatfaal]

 

None the fastest way is called the Sieve of Eratosthenes it involves using an array. It still involves trial division but less off it. First you add two to an array. Then you work through your array testing divisibility. If you get to the end of your array then the number is prime and is pushed to the end of the array. This is a parralelisable operation for instance you can test for the divisibility of all numbers in an array up to the computer resources you have available and then the runtime becomes a polynomial multiple of the resources you have. There is the problem that after a certain point the primes take too much hard drive space so the Sieve of Eratosthenes won't work anymore and you are back to using trial division. The Sieve of Eratosthenes can be used to show that Primes are in P on a turing machine (theoretical computer with infinite resources) P=NP but most computers don't have infinite resources. If you just use multiplication the range of numbers you can possibly calculate on a normal computer decreases by a lot because you are even more limited by hard drive space. There is also a limit on using trial division which is basically if something takes longer than 20 years to calculate your computer will break. There is also the idea that today's limitations may not be limitations in the future new methods of data storage could become available which make just using the sieve the more viable option.

 

the Sieve of Eratosthenes is a prime number finder (ie it finds all the primes within a certain range) - not a method of factorization. The Sieve of Eratosthenes is not even the fastest at doing this once the size of the range / largest number of the range get large ~10^14

 

The fastest way to factor difficult products (those of two primes of a similar size) is the General Number Field Sieve or the Special Number Field Sieve (if your number fits its parameters).

 

Please do not write guesses like P=NP in the main fora - it is irresponsible and misleading.

 

None of your post deals with computational complexity properly

 

https://en.wikipedia.org/wiki/General_number_field_sieve

[Strange]

The sieve of Eratosthenes has nothing to do with factorisation.

 

I think the answer to the question is that the time for each division operation is not the problem; it is the number of operations required.

[imatfaal]

The sieve of Eratosthenes has nothing to do with factorisation.

 

I think the answer to the question is that the time for each division operation is not the problem; it is the number of operations required.

 

Agree completely - I have looked at the Number Field Sieve algorithms and I just cannot work out what is really going on; most of this form of algorithm seem to have a choke point regarding the number of operations required rather than the difficulty of the operations involved.

 

Further to the OP - the really place of study should be Shor's Algorithm; real world quantum computing has arrived. Whilst it is at a pre-difference engine level of development at present it will become viable. Shor's algorithm is proven to work in polynomial time - whereas the General number sieve works in sub-exponential time

[Sensei]

What David proposed in post #2 is not "Sieve of Eratosthenes".

 

Sieve of Eratosthenes pseudocode is

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

 Input: an integer n > 1.
 
 Let A be an array of Boolean values, indexed by integers 2 to n,
 initially all set to true.
 
 for i = 2, 3, 4, ..., not exceeding √n:
   if A[i] is true:
     for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n:
       A[j] := false.
 
 Output: all i such that A[i] is true.

(it's begging for using bitwise logic operations and 8 times decrease memory needed for array)

 

 

What he proposed in post #2 was something like:

list.append( 2 );
for( int i = 3; i < n; i++ )
{
  bool found = false;
  for( int j = 0; j < list.count; j++ )
  {
    if( ( i % list[ j ] ) == 0 ) // modulo
    {
     found = true; // divisible by some prime
     break;
    }
  }
  if( found == false ) list.append( i ); // append yet another prime to array..
}

Output array contains nothing but primes.

 

But better would be to skip the all even numbers, since the beginning:

 

list.append( 2 );
for( int i = 3; i < n; i += 2 )
{
  bool found = false;
  for( int j = 1; j < list.count; j++ )
  {
    if( ( i % list[ j ] ) == 0 ) // modulo
    {
     found = true; // divisible by some prime
     break;
    }
  }
  if( found == false ) list.append( i ); // append yet another prime to array..
}

Edited May 26, 2017 by Sensei

[imatfaal]

What David proposed in post #2 is not "Sieve of Eratosthenes".

 

Sieve of Eratosthenes pseudocode is

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

 Input: an integer n > 1.
 
 Let A be an array of Boolean values, indexed by integers 2 to n,
 initially all set to true.
 
 for i = 2, 3, 4, ..., not exceeding √n:
   if A[i] is true:
     for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n:
       A[j] := false.
 
 Output: all i such that A[i] is true.

(it's begging for using bitwise logic operations and 8 times decrease memory needed for array)

 

 

What he proposed in post #2 was something like:

list.append( 2 );
for( int i = 3; i < n; i++ )
{
  bool found = false;
  for( int j = 0; j < list.count; j++ )
  {
    if( ( i % list[ j ] ) == 0 ) // modulo
    {
     found = true; // divisible by some prime
     break;
    }
  }
  if( found == false ) list.append( i ); // append yet another prime to array..
}

Output array contains nothing but primes.

 

But better would be to skip the all even numbers, since the beginning:

 

list.append( 2 );
for( int i = 3; i < n; i += 2 )
{
  bool found = false;
  for( int j = 1; j < list.count; j++ )
  {
    if( ( i % list[ j ] ) == 0 ) // modulo
    {
     found = true; // divisible by some prime
     break;
    }
  }
  if( found == false ) list.append( i ); // append yet another prime to array..
}

 

OK they both make sense to me - thanks, and well spotted; I must admit I was so annoyed at the fallacies I just skipped the description of the algorithm.

[Strange]

They both sound like implementations of the same algorithm to me.

[TakenItSeriously]

What David proposed in post #2 is not "Sieve of Eratosthenes". Sieve of Eratosthenes pseudocode ishttps://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Input: an integer n > 1.  Let A be an array of Boolean values, indexed by integers 2 to n, initially all set to true.  for i = 2, 3, 4, ..., not exceeding √n:   if A[i] is true:     for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n:       A[j] := false.  Output: all i such that A[i] is true.

(it's begging for using bitwise logic operations and 8 times decrease memory needed for array) What he proposed in post #2 was something like:

list.append( 2 );for( int i = 3; i < n; i++ ){  bool found = false;  for( int j = 0; j < list.count; j++ )  {    if( ( i % list[ j ] ) == 0 ) // modulo    {     found = true; // divisible by some prime     break;    }  }  if( found == false ) list.append( i ); // append yet another prime to array..}

Output array contains nothing but primes.But better would be to skip the all even numbers, since the beginning:

list.append( 2 );for( int i = 3; i < n; i += 2 ){  bool found = false;  for( int j = 1; j < list.count; j++ )  {    if( ( i % list[ j ] ) == 0 ) // modulo    {     found = true; // divisible by some prime     break;    }  }  if( found == false ) list.append( i ); // append yet another prime to array..}

Thanks Sensie, that clarified a lot.

 

BTW, I think you can skip every other 5th integer as well since they all end in a 5. i.e. all primes > 10 end in 1,3,7,9 only. I guess that means every 5th iteration after the odd check.

 

edit to add:

So, I guess I'm asking what would a timer record if placed outside of that modulo check?

 

off topic:

Why do carraige returns keep disappearing when I preview, reply or edit?

Edited May 27, 2017 by TakenItSeriously

[Sensei]

BTW, I think you can skip every other 5th integer as well since they all end in a 5. i.e. all primes > 10 end in 1,3,7,9 only. I guess that means every 5th iteration after the odd check.

It's easy for human because of using decimal system, but computers use binary system, and easily they can skip only 2,4,8,16,2^n etc.

f.e.

255 in binary is %11111111

250 in binary is %11111010

How do you want to skip numbers ending up 0 or 5, without using modulo (at least)?

 

i modulo 5 will be 3rd in internal loop (2,3,5,7,11,....)

and in my optimization, it'll be 2nd in internal loop.

Very quickly found in array and skipped.

Edited May 27, 2017 by Sensei

[TakenItSeriously]

It's easy for human because of using decimal system, but computers use binary system, and easily they can skip only 2,4,8,16,2^n etc.f.e.255 in binary is %11111111250 in binary is %11111010How do you want to skip numbers ending up 0 or 5, without using modulo (at least)?i modulo 5 will be 3rd in internal loop (2,3,5,7,11,....)and in my optimization, it'll be 2nd in internal loop.Very quickly found in array and skipped.

I think mod is fine for small divisors but since the numerator can get large, maybe add a counter in the second loop

k += 1
if k = 5 then
  k = 0
  break
endif

IDK if its any more efficient though.

 

BTW, not sure what language I just used, probably some hybrid lol.

 

edit to add:

That's why I think mod isnt efficient for large numerators with large denominators.

Think of a 64 digit number divided by a 32 digit number.

 

Operations must be expanding expontialy and the number of digits in the example are probably around a 100x too small for 128-bits.

Edited May 27, 2017 by TakenItSeriously

[Sensei]

You don't understand.

There is nothing to skip in internal loop (except "2" in entry list[0], because I incremented i+=2 in outer loop (instead of i++), in "optimized version").

Computer does not know whether f.e.

i=%1 0010 1011 1110 0101 0110 0001

is dividable by 5 or not,

until cpu will reach line

if( ( i % 5 ) == 0 )

5 is in entry list[2], reached very quickly.

 

 

Instead of using built-in type "int" programmer can make custom class Integer, with overloaded operator of modulo,

and implement the whole math dynamically.

If it's in range 32 bits, use unsigned int,

after exceeding 32 bits, use unsigned long long,

after exceeding 64 bits, use dynamically allocated buffer with size limited only by free memory.

Edited May 27, 2017 by Sensei

[TakenItSeriously]

You don't understand.There is nothing to skip in internal loop (except "2" in entry list[0], because I incremented i+=2 in outer loop (instead of i++), in "optimized version").

 

Computer does not know whether f.e.

i=%1 0010 1011 1110 0101 0110 0001

is dividable by 5 or not,

until cpu will reach line

if( ( i % 5 ) == 0 )

5 is in entry list[2], reached very quickly.

Forgive me, I made an error in saying the counter goes in the second loop. I should have said in the first loop after the counter that counts odd numbers only. I think I was thinking in terms of being on the second level.

 

Also you're right, I was confused about binary even being an issue which is ignorance on my part of not knowing the language in your example, much less the syntax which seems to stress fewest characters over readability. A pet peeve of mine since it all gets compiled so why make it an actual code? but "tabs vs spaces" I guess (HBO's Silicon Valley reference).

 

Though I do understand binary for the most part in terms of 2ⁿ combinations or in conversion to/from decimals or even in terms of QM, but not in terms of how most operations are performed on binaries or if distinguishing individual digits in decimal is practical in binary form, but I do get what your saying.

 

I just didn't realize that the "j++" syntax ment change all integers to binary if I interpreted your post correctly.

 

I'm not in the software profession and worked as an EE on the hardware side, though I am naturally gifted at logic and enjoy programming in my own time for personal yet quite extensive projects. However, it's all self taught and limited to the languages I needed most so basically, If I didn't need to use a feature, I probably still need to learn it.

 

So in terms of dynamic type changes, it was mostly as a feature I whished I had many times before it existed. After I had the feature, I've yet to need it which is typical. So I understand why it's needed but I probably wouldn't know it if I saw it, nor any particular details that are important to know about it either..

 

In terms of user-defined classes, I only know a little from VBA experience so thanks for the tip, It was very enlightening. I do have a follow up question if you don't mind at the end.

 

Fortunately, I dont think binary is an issue once we correct my error and place the counter in the first loop, which If I understood your post correctly, initializes the integer as a decimal in the first loop and changes all integers to binary in the second loop. At least I hope thats right.

 

BTW I assume you chose binary for it's efficiency as the native language of computers which I certainly wouldn't argue with either.

 

I hope that clears up any confusion I may have created.

 

As to my quesion on the user-defined classes you showed. How do they pertain to the OS bing 32-bit vs 64-bit as well as the hardware having either 32 i/o signals or 64?

 

I might see it as getting around the OS limitations, but I cant conceive how it gets around the physical limitations of the hardware having only a fixed number of physical signals, not even counting any overhead that may take up some bits.

 

I guess that mostly pertains to that last declaration for over 64 bits. Is this coding for something beyond a typical PC?

Edited May 27, 2017 by TakenItSeriously

[Sensei]

I just didn't realize that the "j++" syntax ment change all integers to binary if I interpreted your post correctly.

 

j++ is shortcut of j=j+1

It means assign value j+1 to variable j.

In other words, increment it by 1.

 

In C/C++ the all integers, everything, are binary, all the time.

Just to display them to user they're converted to ASCII strings.

It's done by f.e. printf().

http://www.cplusplus.com/reference/cstdio/printf/

printf() formatting code "%d" means display decimal number, there are equivalents for hex, floating point, and so on.

If user is entering decimal number, ASCII string must be converted to binary integer/float to computer be able to do any math operation on it.

It's done by f.e. scanf() or sscanf().

http://www.cplusplus.com/reference/cstdio/sscanf/

 

If you have loop

for( int i = 0; i < 10; i++ )

{

printf( "i=%d\n", i );

}

 

It will display i=0,1,2,3,4,5,6,7,8,9

 

j+=2 is shortcut of j=j+2

In other words, increment it by 2.

 

 

If you have loop

for( int i = 0; i < 1000; i += 100 )

{

printf( "i=%d\n", i );

}

 

It will display i=0,100,200,300,400,500,600,700,800,900

 

 

So, when I wrote in 3rd optimized code version:

 

for( int i = 3; i < n; i += 2 )

 

i variable will have assigned 3,5,7,9,11,13,15,17...

 

There is no way to skip yet another 5,10,15,20,25,30,...

It would require adding line:

if( ( i % 5 ) == 0 ) continue;

But 5 is in array at list[2], so such modulo will be executed (in internal loop) very quickly, and skipped

 

 

 

Code:

for( int i = 3; i < n; i += 2 )

{

if( ( i % 5 ) == 0 ) continue;

printf( "i=%d\n", i );

}

would display 3,7,9,11,13,17,19,21,23,27

with 5,15,25,35,.... skipped

Edited May 28, 2017 by Sensei

[John Cuthber]

I'm trying to get a feel for the scale of negative impact that the division operation involved in the factorization of large primes has on computational time.

 

Hypothetically speaking, if you could replace all division operations on large numbers with a multiplication operation on the same numbers instead, while assuming it achieved the same goals of course. What factor increase in efficiency do you think we would gain?

AFAICT, the answer is none.

There's a table here

https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations

If I understand it correctly then the time taken to do division is of the same order as the time for multiplication (if you use this to do the division with)

https://en.wikipedia.org/wiki/Division_algorithm#Newton.E2.80.93Raphson_division

[imatfaal]

AFAICT, the answer is none.

There's a table here

https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations

If I understand it correctly then the time taken to do division is of the same order as the time for multiplication (if you use this to do the division with)

https://en.wikipedia.org/wiki/Division_algorithm#Newton.E2.80.93Raphson_division

 

I think the complexity is of the same order - but that does not mean the time taken for a real world example will be so. I think big O notation works in the limiting case as the numbers tend to infinity; thus the two complexities will be the asymptotically similar but in practice different. In this case, the multiplication is of polynomial complexity and the division is logarithmic * polynomial complexity; when the numbers get very large the polynomial swamps the logarithmic and big O only notes the important fastest growing term.

 

But for any actual calculation, there will always be a greater load for the division than for the multiplication; ie a pair of 20 digit numbers will take very roughly 20 times longer to divide than to multiply

[TakenItSeriously]

I think the complexity is of the same order - but that does not mean the time taken for a real world example will be so. I think big O notation works in the limiting case as the numbers tend to infinity; thus the two complexities will be the asymptotically similar but in practice different. In this case, the multiplication is of polynomial complexity and the division is logarithmic * polynomial complexity; when the numbers get very large the polynomial swamps the logarithmic and big O only notes the important fastest growing term.

 

But for any actual calculation, there will always be a greater load for the division than for the multiplication; ie a pair of 20 digit numbers will take very roughly 20 times longer to divide than to multiply

I think you have a good point that sounds similar to my own line of thinking only I have to think of it in a more mundane way.

 

For example, if I do long division by hand, the first operation to calculate the first digiit of the 2nd factor is an intuitive guess based on the two relative sizes in question which is right most of the time but when it's close, e.g. does it divide 8 times or 9 times? it becomes more and more like a coin flip.

 

But computers, being the most anal thinkers in the Universe can't use intuitive guessing.

 

So, I'm just guessing that they must look at the number of digits, then the left most digit, then the next and the next and so on.

 

Then it must repeat the entire process for calculating the next digit. which makes it an exponential expansion.

 

I always thought of that as the extra loading though I don't actually know what the actual algorythm looked like, especially for binary numbers. like there might be some mathetical rules I'm not aware of going on.

 

Also the operation seems to require looking at the entire number as a whole whereas all other operations seem to be able to to be broken down into pieces. So how it must be handled using different memory types which is something else I don't know about how computers handle it, though Sensei's post touched on multiple class types.

 

Possibly something going on at the chip logic level such as with math coprocessors.

 

Edit to add:

If someone can code a simple test we could measure this to find out.

 

example generic code

b = the largest integer your code allows
a = some big number with half number the digits -1 digit
c = average value of x in the first loop.
n = some big number to increase the resolution of the timers and to test a fair sample size of a.
. .   
report StartTime
. .
for i = 1 to n do
  x = b/a
  a = a+1
end. . 

report SplitTime
re-initialize a
. .   
for i =1 to n do
  y = a*c
  a = a+1
end. .
report EndTime

The timer should be the kind accurate down to 5ms, not the second timer.

 

This would test the processor time for the first 32-bits. I don't know how to code for testing the other class types.

Edit to add again:

Also, Sensei's posts had gotten me to think more along the lines of binary numbers, which I suppose is the nature of c's efficiency advantage.

 

Therefore I suppose there is an associated lagg time that comes from converting decimals to binary that should be taken into account.

 

However, I think we might be able to look at it as lagtime effect or an additive component that must occur for both operations vs any multiplication component that I'm actually more concerned about.

 

I have some additional questions about binary numbers which I may post in a different thread. I don't want the topic to wander too far off base.

Though binary numbers may be too integral to the topic that we cannot seperate the two.

Edited May 31, 2017 by TakenItSeriously

[Sensei]

I think the complexity is of the same order - but that does not mean the time taken for a real world example will be so. I think big O notation works in the limiting case as the numbers tend to infinity; thus the two complexities will be the asymptotically similar but in practice different. In this case, the multiplication is of polynomial complexity and the division is logarithmic * polynomial complexity; when the numbers get very large the polynomial swamps the logarithmic and big O only notes the important fastest growing term.

 

But for any actual calculation, there will always be a greater load for the division than for the multiplication; ie a pair of 20 digit numbers will take very roughly 20 times longer to divide than to multiply

 

Multiplication can be implemented as series of left-bit shift operations.

#include <stdio.h>
#include <stdlib.h>

int main( int argc, int *argv[] )
{
    if( argc == 3 )
    {
        int src1 = atoi( (const char *) argv[ 1 ] );
        int src2 = atoi( (const char *) argv[ 2 ] );
        int output = 0;
        for( int i = 0; i < 32; i++ )
        {
            if( src1 & ( 1 << i ) )
            {
                output += src2 << i; // add to final src2 * 2^i
            }
        }
        printf( "%d\n", output );
    }
    return( 0 );
}

 

When number of bits is constant, loop can be unrolled:

 

#include <stdio.h>
#include <stdlib.h>

int main( int argc, int *argv[] )
{
    if( argc == 3 )
    {
        int src1 = atoi( (const char *) argv[ 1 ] );
        int src2 = atoi( (const char *) argv[ 2 ] );
        int output = 0;
        if( src1 & 0x1 ) output += src2;
        if( src1 & 0x2 ) output += src2<<1;
        if( src1 & 0x4 ) output += src2<<2;
        if( src1 & 0x8 ) output += src2<<3;
        if( src1 & 0x10 ) output += src2<<4;
        if( src1 & 0x20 ) output += src2<<5;
        if( src1 & 0x40 ) output += src2<<6;
        if( src1 & 0x80 ) output += src2<<7;
        // ...repeat 32 times, or as many as is needed....
        printf( "%d\n", output );
    }
    return( 0 );
}

CPU can have such unrolled loop implemented in hardware.

 

ps. Please notice that src1*src2, will be executed in completely different time than src2*src1, even though result will be the same, if number of set bits is significantly higher.

 

 

Division can be also implemented as series of bit-shift operations:

#include <stdio.h>
#include <stdlib.h>

int main( int argc, int *argv[] )
{
    if( argc == 3 )
    {
        int src1 = atoi( (const char *) argv[ 1 ] );
        int src2 = atoi( (const char *) argv[ 2 ] );
        int output = 0;

        printf( "%d / %d = %d\n", src1, src2, src1 / src2 );

        if( src2 == 0 )
        {
            // division by 0
        }
        else if( src1 == src2 )
        {
            output = 1;
        }
        else
        {
            int shifts = 0;
            while( src1 > src2 )
            {
                src2 <<= 1;
                shifts++;
            }

            do
            {
                src2 >>= 1;
                shifts--;

                //printf( "Src1 %d Src2 %d Shifts %d\n", src1, src2, shifts );

                if( src1 >= src2 )
                {
                    src1 -= src2;
                    output += 1 << shifts;
                }
            } while( shifts > 0 );
        }
        printf( "%d\n", output );
    }
    return( 0 );
}

ps2. Algorithms for unsigned integers.

Edited June 1, 2017 by Sensei

[imatfaal]

 

Multiplication can be implemented as series of left-bit shift operations.

...

 

Not sure I could make it through the pseudocode if I tried. The crux of the matter is that the calculational complexity of multiplication is similar to that of division in that the fastest growing term in the complexity of division is a multiplication operation. However, for any calculation of actual time used the division will take about Log(n) times longer - this is because the calculationally fastest method of division for large numbers is to take the reciprocal of one and then multiply by the other; so how ever quick you make the multiplication the division is always longer because you have to take the reciprocal as well as doing the multiplication.

[Sensei]

Not sure I could make it through the pseudocode if I tried.

They are not pseudocode. But the real C/C++ working codes.

Which row you are not sure? I will tell you what it does.

I attached projects, that can be loaded in Visual Studio Express/Community, and compiled by yourself.

 

Multiply.zip

 

Divide.zip

 

In Release folder there are ready compiled executables for 32 bit.

Run them from command-line (cmd.exe) with two arguments, unsigned integers.

 

The crux of the matter is that the calculational complexity of multiplication is similar to that of division in that the fastest growing term in the complexity of division is a multiplication operation. However, for any calculation of actual time used the division will take about Log(n) times longer - this is because the calculationally fastest method of division for large numbers is to take the reciprocal of one and then multiply by the other; so how ever quick you make the multiplication the division is always longer because you have to take the reciprocal as well as doing the multiplication.

 

To be able to calculate 1/x we would have to be working with real numbers, with floating point, isn't.. ?

How do you want to implement 1/x for integers/unsigned integers, without having fractional part.. ?

 

My algorithms are working with unsigned integers (and after small modifications could be used with signed integers).

 

As we can see, in the worst scenario, multiplication of n-bits will have to execute n-times of bitwise AND operator, n-times addition, 2*n-times left-bit shift (arithmetic shift without carry)

https://en.wikipedia.org/wiki/Bitwise_operation#Arithmetic_shift

 

So 32 bit multiplied by 32 bit will need 32 times AND,32 times addition, 64 times left-bit shift. Result 64 bit long.

64 bit multiplied by 64 bit will need 64 times AND,64 times addition, 128 times left-bit shift. Result 128 bit long.

 

Division of 64 bit by 32 bit will need in the worst scenario

64 left-bit shift operations,

32 right-bit shift operations,

64 additions (32 of them increment by 1)

64 subtractions (32 of them decrement by 1).

 

(it could be slightly optimized with less operations needed, it was rough algorithm)

 

Tell me how would you implement multiplication of unsigned integers, if you would have such task to do.

Edited June 2, 2017 by Sensei

[imatfaal]

Sensei - the difference in our approaches is that I am looking at this from a theoretical calculational complexity / Big O viewpoint whereas you are looking at it as a practical computational complexity / C++ perspective; both are, of course, equally valid. At very large numbers and serious computing power the two concepts will converge - but it is very difficult to compare one to the other without two sets of code or two sets of complexity calculations; and I just do not have the knowledge for that.