The Karatsuba algorithm is a fast multiplication algorithm that uses a divide and conquers approach to multiply two n-digit numbers. Here, the system compiler takes lesser time to compute the product than the time-taken by a normal multiplication. The divide-and-conquer algorithm reduces the multiplication of two n-digit numbers to three multiplications of n/2-digit numbers and, by repeating this reduction, to at most single-digit multiplications. It is therefore asymptotically faster than the traditional algorithm, which performs single-digit products. The Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic “grade school” algorithm. Multiplying large numbers efficiently is an important task; however, the traditional, naive way of multiplying numbers involves multiplying each digit in one number to each digit in the second number. Aesthesis of multiplication increases the time required to solve using the naive way increases dramatically. Functional techniques have been proposed in a plethora of research; nevertheless, all of these approaches have three major flaws: First, ASIC hardware is the intended use for the great majority of flawed multipliers and divisions available today. Consequently, due to the primary architectural distinctions between the two, tailored ASICs have not yielded the same outcomes when moved to FPGAs by means of direct synthesis. Secondly, regular approximations units are often used instead of state-of- the-art (SoA) ones in an application with many kernels. Furthermore, rather than relying on the total performance, end-to-end evaluation is based on the Quality of Returns (QoR).

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Karatsuba Algorithm: A Paradigm Shift in Multiplication Efficiency

  • Sivanagireddy Kalli,
  • S. Chamandi Priya

摘要

The Karatsuba algorithm is a fast multiplication algorithm that uses a divide and conquers approach to multiply two n-digit numbers. Here, the system compiler takes lesser time to compute the product than the time-taken by a normal multiplication. The divide-and-conquer algorithm reduces the multiplication of two n-digit numbers to three multiplications of n/2-digit numbers and, by repeating this reduction, to at most single-digit multiplications. It is therefore asymptotically faster than the traditional algorithm, which performs single-digit products. The Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic “grade school” algorithm. Multiplying large numbers efficiently is an important task; however, the traditional, naive way of multiplying numbers involves multiplying each digit in one number to each digit in the second number. Aesthesis of multiplication increases the time required to solve using the naive way increases dramatically. Functional techniques have been proposed in a plethora of research; nevertheless, all of these approaches have three major flaws: First, ASIC hardware is the intended use for the great majority of flawed multipliers and divisions available today. Consequently, due to the primary architectural distinctions between the two, tailored ASICs have not yielded the same outcomes when moved to FPGAs by means of direct synthesis. Secondly, regular approximations units are often used instead of state-of- the-art (SoA) ones in an application with many kernels. Furthermore, rather than relying on the total performance, end-to-end evaluation is based on the Quality of Returns (QoR).