Publication

Faster Integer Multiplication

2009
Conference Papers

Abstract

For more than 35 years, the fastest known method for integer multiplication has been the Schonhage-Strassen algorithm running in time O(n log n log log n). Under certain restrictive conditions, there is a corresponding Omega(n log n) lower bound. All this time, the prevailing conjecture has been that the complexity of an optimal integer multiplication algorithm is Theta(n log n). We take a major step towards closing the gap between the upper bound and the conjectured lower bound by presenting an algorithm running in time n log n2(O)(log* n). The running time bound holds for multitape Turing machines. The same bound is valid for the size of Boolean circuits.

Official source

https://infoscience.epfl.ch/entities/publication/aa410ee6-e9c4-4cf2-b6e5-f7b6596eb076

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

2009
Conference Papers

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/aa410ee6-e9c4-4cf2-b6e5-f7b6596eb076

About this result

Related concepts (31)

Multiplication algorithm

A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are more efficient than others. Efficient multiplication algorithms have existed since the advent of the decimal system. If a positional numeral system is used, a natural way of multiplying numbers is taught in schools as long multiplication, sometimes called grade-school multiplication, sometimes called the Standard Algorithm: multiply the multiplicand by each digit of the multiplier and then add up all the properly shifted results.

Multiplication

Multiplication (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four elementary mathematical operations of arithmetic, with the other ones being addition, subtraction, and division. The result of a multiplication operation is called a product. The multiplication of whole numbers may be thought of as repeated addition; that is, the multiplication of two numbers is equivalent to adding as many copies of one of them, the multiplicand, as the quantity of the other one, the multiplier; both numbers can be referred to as factors.

Boolean circuit

In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible input length. Boolean circuits are defined in terms of the logic gates they contain. For example, a circuit might contain binary AND and OR gates and unary NOT gates, or be entirely described by binary NAND gates. Each gate corresponds to some Boolean function that takes a fixed number of bits as input and outputs a single bit.

Related publications (32)

Faster Integer Multiplication

Chat with Graph Search

Additive and geometric transversality of fractal sets in the integers

EdgeAI-Aware Design of In-Memory Computing Architectures

In Medio Stat Virtus: Combining Boolean and Pattern Matching