Question

School Method for Integer Addition and Karatsuba Algorithm for Integer Multiplication

Integer Division

Your program takes one line as input. The input line contains three integers separated by spaces. Let

the three integers be I1, I2, and B. I1 and I2 are both nonnegative integers up to 100 digits long (there are

no leading 0s, except when the value itself is 0). B is I1 and I2's base (B is from 2 to 10).1

Your program should output the sum of I1 and I2, using the school method, then the product of I1 and

I2, using the Karatsuba algorithm, and _nally the ratio between I1 and I2 (rounded down). You are asked

to come up with a way to perform this division. I2 will not be 0.

The results should still use base B. B is Base (for example 2,3,4,5,6,7,8,9,10 etc.)

output should verify on these cases:

Output at:

Output at:

For input 203304113112320313010342344201000044101413303023100020144430002114444213113311213134343432001320143 20 5

.

Output shouldbe 203304113112320313010342344201000044101413303023100020144430002114444213113311213134343432001320213 4121132312301411310212402434020001432033321111012000403444100042344434312321224313242424140031403410 10140203130341013123014342210022224430043140123402223232221222330444433130413033131442144100041004

.

.

For input 2050152115105155004531243354030222541554132345035432034314321130543434551311300534 32133240421554152303304135 6

.

Output shouldbe 2050152115105155004531243354030222541554132345035432034350454411405433144015005113 111213135224431431034143500544014250351452252413033422051245553330330303322453014515113313053024124501255102 34451252405541351255411135233311325320214123545031144020

.

.

For input 22434323311222344001420202110322420131201144213434334 3323431401132310013041210130334020134042123200 5

.

Output shouldbe 22434332140204300134230220202033101020221333311113034 143021223440122141030300224441100332232201230444013200010012344222122200312011003424310414231214300 3221200

.

.

For input 152302323413310315221244042001424110153154014124553 13032302554053232402422421310 6

.

Output shouldbe 152302323413310315221301114304422203430000440550303 2515040333031050342333340305545110155043213151142151510312503555311051420441230 11311041011113320552553

.

.

For input 623363501374320636132422004554500732247124426105664512315102244634425276375765670531161 43156047430 8

.

Output shouldbe 623363501374320636132422004554500732247124426105664512315102244634425276376031046600611 33600314367421163157071730456244367563136251235307215645357437647656325125015044360313724442314630 13352173110062224612240540335061624403117527267735042463621677661656572316560

.

.

For input 640356602542982887461446438005210848507222245132398471042649185213049 3801312861312886925997022577262081884 10

.

Output shouldbe 640356602542982887461446438005214649820083558019324468065226447294933 2434195789073265364321683072671475632036896590066228483766752989688411259539066159761966350818973823304316 168456695332837796087717979581935

Answer 1

#Welcome to Chegg

l1, l2, B = input().split()
l1 = int(l1)
l2 = int(l2)
B = int(B)

def val(c):
    if c >= '0' and c <= '9':
        return ord(c) - ord('0')
    else:
        return ord(c) - ord('A') + 10

def toInt(num, B):
    length = len(num)
    power = 1      #Initialize power of base
    result = 0     #Initialize result

    # Multiply the number repeatedly by its power to get its decimal equivalent
    for i in range(length - 1, -1, -1):
        result += val(num[i]) * power
        power = power * B
    return result

l1_int = toInt(str(l1), B)
l2_int = toInt(str(l2), B)

school_sum = l1_int + l2_int

#Following function returns the string with zeros padded
def zeroPad(numString, zeros, left=True):
    for i in range(zeros):
        if(left):
            numString = '0' + numString
        else:
            numString = numString + '0'
    return numString

#Following function multiplies two integers using Karatsuba's algorithm
def karatsuba_mul(num1, num2):
    #convert integers to strings
    num1 = str(num1)
    num2 = str(num2)

    #base case for recursion
    if len(num1) == 1 and len(num2) == 1:
        return int(num1) * int(num2)

    if len(num1) < len(num2):
        num1 = zeroPad(num1, len(num2) - len(num1))

    elif len(num2) < len(num1):
        num2 = zeroPad(num2, len(num1) - len(num2))
    n = len(num1)
    j = n//2

    #for odd digit integers add 1
    if (n % 2) != 0:
        j += 1

    BZeroPadding = n - j
    AZeroPadding = BZeroPadding * 2

    #Divide the two numbers into halves:
    a = int(num1[:j])
    b = int(num1[j:])
    c = int(num2[:j])
    d = int(num2[j:])

    #recursively calculate
    ac = karatsuba_mul(a, c)
    bd = karatsuba_mul(b, d)
    k = karatsuba_mul(a+b, c+d)
    A = int(zeroPad(str(ac), AZeroPadding, False))
    B = int(zeroPad(str(k - ac - bd), BZeroPadding, False))
    return A + B + bd

karat_mul = karatsuba_mul(l1_int, l2_int)

ratio = int(l1_int/l2_int)

def reVal(num):
    if (num >= 0 and num <= 9):
        return chr(num + ord('0'))
    else:
        return chr(num - 10 + ord('A'))

def fromInt(num, B):
    result = ''

    # Convert the number into original base by repeatedly dividing it by base and taking remainder
    while (num > 0):
        result += reVal(num % B)
        num = int(num / B)

    # Reverse the result
    result = result[::-1]
    return result

school_sum = fromInt(school_sum, B)
karat_mul = fromInt(karat_mul, B)
ratio = fromInt(ratio, B)

#Finally print the following quantities
print(school_sum, '\n', karat_mul, '\n', ratio)

Sample output is shown below:

Answer 2

To solve the given problem, we need to perform addition, multiplication, and division operations on integers represented in base B using the school method for addition and the Karatsuba algorithm for multiplication. We also need to implement a division algorithm.

Here's a Java program that takes the input as specified and performs the required operations:

import java.util.Scanner;

public class IntegerOperations {

    

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        String input = scanner.nextLine();

        scanner.close();

        

        String[] numbers = input.split(" ");

        String I1 = numbers[0];

        String I2 = numbers[1];

        int B = Integer.parseInt(numbers[2]);

        

        // Perform addition using the school method

        String sum = add(I1, I2, B);

        System.out.println(sum);

        

        // Perform multiplication using the Karatsuba algorithm

        String product = multiply(I1, I2, B);

        System.out.println(product);

        

        // Perform division

        String quotient = divide(I1, I2, B);

        System.out.println(quotient);

    }

    

    public static String add(String I1, String I2, int B) {

        // Convert the numbers to arrays of digits

        int[] num1 = convertToDigits(I1);

        int[] num2 = convertToDigits(I2);

        

        int carry = 0;

        StringBuilder sum = new StringBuilder();

        

        // Perform school method addition

        int i = num1.length - 1;

        int j = num2.length - 1;

        

        while (i >= 0 || j >= 0 || carry > 0) {

            int digit1 = (i >= 0) ? num1[i] : 0;

            int digit2 = (j >= 0) ? num2[j] : 0;

            

            int total = digit1 + digit2 + carry;

            int digitSum = total % B;

            carry = total / B;

            

            sum.insert(0, digitSum);

            

            i--;

            j--;

        }

        

        return sum.toString();

    }

    

    public static String multiply(String I1, String I2, int B) {

        // Convert the numbers to arrays of digits

        int[] num1 = convertToDigits(I1);

        int[] num2 = convertToDigits(I2);

        

        // Perform multiplication using Karatsuba algorithm

        int[] result = karatsubaMultiply(num1, num2, B);

        

        StringBuilder product = new StringBuilder();

        for (int digit : result) {

            product.append(digit);

        }

        

        return product.toString();

    }

    

    public static String divide(String I1, String I2, int B) {

        // Convert the numbers to arrays of digits

        int[] num1 = convertToDigits(I1);

        int[] num2 = convertToDigits(I2);

        

        // Perform division

        int[] quotient = division(num1, num2, B);

        

        StringBuilder result = new StringBuilder();

        for (int digit : quotient) {

            result.append(digit);

        }

        

        return result.toString();

    }

    

    // Helper method to convert a string of digits to an array of integers

    public static int[] convertToDigits(String number) {

        int[] digits = new int[number.length()];

        

        for (int i = 0; i < number.length(); i++) {

            digits[i] = Character.getNumericValue(number.charAt(i));

        }

        

        return digits;

    }

    

    // Helper method to perform multiplication using the Karatsuba algorithm

    public static int[] karats