在时间复杂度小于O(N)的情况下，在不使用*运算符和不使用逐位的情况下将两个数字相乘

Question

我需要一种算法来将两个数字相乘，而不使用乘法（*）运算符，也不使用复杂度小于O（N）的逐位运算，我提出了最明显的算法，即

int m = 6, n = 5, sum = 0;
for(int i = 0, i<n, i++)
    sum += m;

但这是O（N），对我不起作用。

Answer 1

我有以下解决方案

public static int mult(int m, int n) {
        int amount = 1;
        int bSum = 0;
        int sum = 0;
        int current = m;
        while (bSum + amount <= n) { 
            sum += current;
            current = current + current;
            bSum += amount;
            amount = amount + amount;
        }
        // bSum = 1+2+4+ ... + 2^k = 2^(k+1) - 1
        // cycle pass log(n) times
        if (bSum < n) {
            sum += mult(m, n - bSum); // n - bSum less n/2
        }
        return sum;
    }

复杂度为O（log（n）+log（n/2）+log（n/4）+…）=O（日志（n）+log（n）-log（2）+log。总和中的日志（n）总数为O（log（n））。从这个解决方案的最终复杂性O（log^2（n））。

Answer 2

谢谢大家，我找到了一个简单的解决方案：

static ulong Mul(uint N, uint M)
    {   if (N == 0)
            return 0;
        if (N == 1)
            return M;
        ulong res;
        res = Mul(N / 2, M);
        if (N % 2 == 0)
            return res+res;
        else
            return res+res+M;
        }

Answer 3

以下是Python中的递归解决方案：

import math
def fast_multiply(m, n):
    if n == 0: return 0
    shift_by = len("{0:b}".format(n)) - 1
    remainder = n - (1 << shift_by)
    return (m << shift_by) + fast_multiply(m, remainder)

这在O（log（n））中运行，因为在递归树中最多有log（n）级别，只有一个递归调用，而O（1）在递归调用之外工作。

Answer 4

它的迭代请参阅链接以获得解释。

def multiply(x, y):
    if y < 0:
        return -multiply(x, -y)
    elif y == 0:
        return 0
    elif y == 1:
        return x
    else:
        return x + multiply(x, y - 1)

以下是一步一步解释Visualize Python代码执行的链接，您可以看到每个步骤，直到获得输出

Answer 5

#include <bits/stdc++.h>
  
using namespace std;
int multiply(int a,int b)
{
  int temp;
  if( a == 0){
     return 0;
  }
  if( a == 1){
     return b;
   }
   temp = multiply(a/2, b);
   if (a % 2 == 0){
      return temp + temp;
   }
   else{
       return temp+temp+b;
     }
   }
 int main(){
 int a,b;
 cin>>a>>b;
 cout<<multiply(a,b)<<endl;
 return 0;
 }