2023 - T3 - WS1 - Special Week

Collection 2023 - T3 - WS1 - Special Week

Organizer(s) van der Hoeven, Joris ; Giesbrecht, Mark ; Koiran, Pascal ; Villard, Gilles

Date(s) 18/09/2023 - 22/09/2023

linked URL https://indico.math.cnrs.fr/event/8113/

11 11

General audience presentation - Integer multiplication in time $O(n \log n)$

By Joris van der Hoeven

Integer multiplication is one of the oldest mathematical operations and still a central problem for computer arithmetic. The complexities of many other basic operations such as division, base conversion, gcds, computing $e$ and $\pi$, FFTs, etc. can be expressed in terms of the complexity of integer multiplication. In our talk, we will survey a new algorithm for multiplying two n-digit integers in time $O(n \log n)$.

Information about the video

Date of recording 20/09/2023
Date of publication 20/09/2023
Institution IHP
Language English
Audience Researchers, Graduate Students, Students
Director(s) Alexandre Duplessis
Format MP4
Venue IHP - Hermite Amphitheater

Citation data

DOI 10.57987/IHP.2023.T3.WS1.SW.003
Cite this video van der Hoeven, Joris (20/09/2023). General audience presentation - Integer multiplication in time $O(n \log n)$. IHP. Audiovisual resource. DOI: 10.57987/IHP.2023.T3.WS1.SW.003
URL https://dx.doi.org/10.57987/IHP.2023.T3.WS1.SW.003

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow

All the collection videos

published on September 18, 2023

Efficient algorithms for integer and polynomial matrices - Part 1

By George Labahn , Arne Storjohann

published on September 18, 2023

Efficient algorithms for integer and polynomial matrices - Part 2

By George Labahn , Arne Storjohann

published on September 19, 2023

Efficient algorithms for integer and polynomial matrices - Part 3: Linear algebra over ℤ and K[𝑥]

By George Labahn , Arne Storjohann

published on September 19, 2023

Efficient algorithms for integer and polynomial matrices - Part 4: Introduction to some Matrix Normal Forms

By George Labahn , Arne Storjohann

published on September 21, 2023

Efficient algorithms for integer and polynomial matrices - Part 5: More on Hermite Normal Form (focus on integer matrices)

By George Labahn , Arne Storjohann

published on September 21, 2023

Efficient algorithms for integer and polynomial matrices - Part 6: Fast Hermite Form Computation for polynomial matrices (also fast determinant)

By George Labahn , Arne Storjohann

published on September 22, 2023

Efficient algorithms for integer and polynomial matrices - Part 7: Fast Hermite Normal Form Computation (integer case)

By George Labahn , Arne Storjohann

published on September 22, 2023

Efficient algorithms for integer and polynomial matrices - Part 8: Computing the Smith form with multipliers of a nonsingular integer matrix

By George Labahn , Arne Storjohann

published on September 19, 2023

Euclidean Lattices - Part 1

By Damien Stehlé

published on September 20, 2023

Euclidean Lattices - Part 2

By Damien Stehlé

$General audience presentation - Integer multiplication in time $O(n \log n)$$

published on September 20, 2023

General audience presentation - Integer multiplication in time $O(n \log n)$

By Joris van der Hoeven

Copyright Carmin.tv 2024

Give feedback