My Math Forum  

Go Back   My Math Forum > Math Forums > Math

Math General Math Forum - For general math related discussion and news

Thanks Tree9Thanks
  • 4 Post By v8archie
  • 3 Post By Denis
  • 2 Post By topsquark
LinkBack Thread Tools Display Modes
April 9th, 2019, 06:18 AM   #1
Math Team
Joined: Dec 2013
From: Colombia

Posts: 7,683
Thanks: 2664

Math Focus: Mainly analysis and algebra
Quick Multiplication

It seems that we can now multiply somewhat more quickly than before.
Thanks from topsquark, romsek, Joppy and 1 others
v8archie is offline  
April 9th, 2019, 08:27 AM   #2
Math Team
Joined: Oct 2011
From: Ottawa Ontario, Canada

Posts: 14,597
Thanks: 1038

Easier to get a rabbit: "rabbits multiply quickly"!
Thanks from Maschke, topsquark and Joppy
Denis is offline  
April 9th, 2019, 10:09 AM   #3
Math Team
topsquark's Avatar
Joined: May 2013
From: The Astral plane

Posts: 2,271
Thanks: 934

Math Focus: Wibbly wobbly timey-wimey stuff.
Will somebody get me a pitchfork or something so we can put an end to him?

Thanks from Denis and Joppy
topsquark is offline  
April 9th, 2019, 06:00 PM   #4
Senior Member
Joined: Sep 2016
From: USA

Posts: 645
Thanks: 408

Math Focus: Dynamical systems, analytic function theory, numerics
Originally Posted by v8archie View Post
It seems that we can now multiply somewhat more quickly than before.
I saw this paper a few weeks ago and was completely baffled since I had already thought that modern FFT algorithms achieved $\mathcal{O}(n \log n)$. It turns out if you chase down the analysis, there is also a $\log \log n$ term hiding in there that arises from a minor preprocessing step.

This algorithm won't actually be practically faster though since it takes an absolutely enormous $n$ before the $\log \log n$ causes the FFT-based algorithm to be slower. Its still really cool though.
SDK is offline  

  My Math Forum > Math Forums > Math

multiplication, quick

Thread Tools
Display Modes

Similar Threads
Thread Thread Starter Forum Replies Last Post
Multiplication Help gazing600000 Algebra 14 January 27th, 2013 11:35 AM
Multiplication tallbabe1 Algebra 1 January 27th, 2013 11:17 AM
multiplication hansFlyers Abstract Algebra 9 October 8th, 2012 04:38 AM
Set Multiplication jstarks4444 Number Theory 0 December 31st, 1969 04:00 PM

Copyright © 2019 My Math Forum. All rights reserved.