Introduction to number theory lecture 15. Numerical calculation

Item: Introduction to number theory lecture 15. Numerical calculation
Rating: 5
Author: PostSingularity Institute

by Richard E Borcherds

Formal & Physical Sciences Mathematics PBMathematics PBHNumber theory

🎙 Richard E Borcherds 👥 82K 📅 February 7, 2022 ⏱ 40 min 👁 8K 📄 lecture 🧭 2026-08-17

Available in: English (current) Français

Keywords

big O notationEuclid's algorithmChinese remainder theoremfast Fourier transformRussian peasant multiplication

Summary

This lecture introduces methods for efficient numerical computation in number theory. The speaker begins by emphasizing the importance of speed when dealing with large numbers, often hundreds of digits. He introduces the big O notation to estimate running times, distinguishing between polynomial-time and exponential-time algorithms. He then discusses algorithms for basic operations: addition is O(n), while the standard multiplication algorithm is O(n^2). Surprisingly, faster multiplication methods exist, such as the fast Fourier transform (FFT) and a method based on the Chinese remainder theorem (CRT). The CRT method reduces numbers modulo many small primes, performs multiplications modulo each prime, and reconstructs the result using the CRT. This approach is particularly efficient for computations involving only addition, subtraction, and multiplication, like computing determinants, and it allows for parallel processing. The speaker also warns about the practical insignificance of log log n factors and the impact of hardware and memory access on actual running times. He discusses the historical evolution of computational capabilities, from a million operations being trivial in the 1960s to trillions being trivial today, and mentions the potential of quantum computers and specialized hardware. Finally, he explains the Russian peasant multiplication algorithm and its generalization to fast exponentiation (a^b mod m) using repeated squaring.

204 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides valuable insights into algorithmic efficiency in number theory, with clear explanations and practical examples. The argumentation is solid: the speaker justifies the need for fast algorithms, explains the big O notation, and demonstrates the CRT-based multiplication method with a concrete determinant example. He also critically evaluates the practical relevance of theoretical complexity estimates, noting that log log n factors are often negligible and that hardware constraints can dominate. The discussion of parallel processing and specialized hardware adds practical depth. The speaker’s authority and clear presentation strengthen the value of the content.

Scientific Rigor, Source Quality, Title Accuracy

The lecture is scientifically rigorous, with precise definitions and correct mathematical statements. The speaker references the standard textbook ‘An Introduction to the Theory of Numbers’ by Niven, Zuckerman, and Montgomery, and provides a correction to a claim about the CRT method’s efficiency. The title accurately reflects the content, focusing on numerical calculation in number theory. The lecture is well-structured and suitable for an undergraduate course, but it also offers depth for more advanced viewers. No comments were provided for analysis.

189 words

Title / Content Match

The title accurately reflects the content: a lecture on numerical calculation in number theory, focusing on algorithms and complexity.

Quality & Reliability

9/10

Lecture by a renowned mathematician (Fields Medalist) with clear explanations, corrections, and references to standard textbook. Content is mathematically sound and well-structured.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

Course playlist: Introduction to number theory — Mentioned as the playlist for the course lectures.
An Introduction to the Theory of Numbers — Textbook by Niven, Zuckerman, and Montgomery (5th edition), referenced as the course textbook.

Concurring Sources

Introduction to Algorithms (CLRS) — Standard reference for algorithm analysis, including big O notation and fast multiplication.

Contribution & Novelties

The lecture provides a clear and accessible introduction to algorithmic complexity in number theory, with a focus on practical implications. It highlights the surprising existence of sub-quadratic multiplication algorithms and explains the Chinese remainder theorem method in detail, which is often not covered in introductory courses. The discussion of parallel processing and the historical context of computational limits adds unique value.

Pour aller plus loin :

Fast Fourier transform — The FFT is a key algorithm for fast multiplication and signal processing.
Chinese remainder theorem — The CRT is used in the modular multiplication method described.
Big O notation — Essential for analyzing algorithm complexity.
Modular exponentiation — The fast exponentiation method discussed is a form of modular exponentiation.

119 words

Radar Profile

The radar profile shows high scores in information quantity, quality, and technical level, with slightly lower but still high reliability. This indicates a dense, well-explained lecture with strong mathematical content, suitable for an advanced undergraduate audience.

Reliability 9/10