algorithm - 加算による乗算をシミュレートするアルゴリズム

Question

加算による乗算をシミュレートするアルゴリズムを設計する方法。2つの整数を入力します。それらはゼロ、正または負の場合があります。

Answer 1

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

Answer 2

いくつかの擬似コード：

function multiply(x, y)
  if abs(x) = x and abs(y) = y or abs(x) <> x and abs(y) <> y then sign = 'plus'
  if abs(x) = x and abs(y) <> y or abs(x) <> x and abs(y) = y then sign = 'minus'

 res = 0
 for i = 0 to abs(y)
  res = res + abs(x)
 end

 if sign = 'plus' return res
    else return -1 * res

end function

Answer 3

val:= 0
bothNegative:=false

if(input1 < 0) && if(input2 < 0)
  bothNegative=true
if(bothNegative)
  smaller_number:=absolute_value_of(smaller_number)
for [i:=absolute_value_of(bigger_number);i!=0;i--]
do val+=smaller_number

return val;

Answer 4

    mul(a,b)
    {
    sign1=sign2=1;
    if(a==0 || b==0)
return 0;
if(a<0){
    sign1=-1;
    a=-a;
    }
    if(b<0){
    sign2=-1;
    b=-b;
    }
    s=a;
    for(i=1;i<b;i++)
    s+=a;
    if(sign1==sign2)
    return s;
    else
    return -s;
    }

Answer 5

整数の場合はどうですか？

int multiply(int a, int b)
{
    int product = 0;
    int i;
    if ( b > 0 )
    {
        for(i = 0; i < b ; i++)
        {
            product += a;
        }
    }
    else
    {
        for(i = 0; i > b ; i--)
        {
            product -= a;
        }
    }

    return product;
}

Answer 6

演算を使わずに乗算アルゴリズムを探していたのでここに来ました*。ここに表示されるのは、数値をn回加算または減算することだけです。O（n）で大丈夫ですが...

演算がある場合は、乗算用のO（log n）アルゴリズムをbitwise shift取得できます。

これが私の擬似コードです：

function mul(n, x)
    if n < 0 then   # 'n' cannot be negative
        n := -n
        x := -x
    endif

    y := 0
    while n != 0 do
        if n % 2 == 0 then
            x := x << 1     # x := x + x
            n := n >> 1     # n := n / 2
        else
            y := y + x
            x := x << 1     # x := x + x
            n := n - 1      # n := (n-1)/2
            n := n >> 1
        endif
    endwhile

    return y                # y = n * x
end

上記の関数mul(1000000, 2)はO（log 1000000）であり、formul(2, 1000000)はO（log 2）のみであることに注意してください。

もちろん、同じ結果が得られますが、関数呼び出しのパラメーターの順序が重要であることに注意してください。

編集：使用するための補足n % 2

n % 2使用の実装bitwise shift

それはかなり簡単です。最初nに2で割り、次に2を掛けて、変更されているnかどうかを確認します。n擬似コード：

function is_even(n)
    n_original := n
    n := n >> 1        # n := n / 2
    n := n << 1        # n := n * 2
    if n = n_original then
        return true    # n is even
    else
        return false   # n is not even
    endif
end

n % 2使用の実装bitwise and

function is_even(n)
    if n and 1 = 0 then
        return true
    else
        return false
    endif
end