Hacker News Reader

Comment by burk96 | Hacker News Reader

I'm making my way through uni currently. I've taken a few CS classes that have touched briefly on O notation and I am currently in Calc 2. I understand bits and pieces of this but I am lost in most of the paper. What courses should I be taking to better my understanding of papers of this sort? Or alternatively, are there any online resources that could help me work my way through research papers like these?

View on HN

You can learn all of these ideas on your own (by e.g. going through textbooks and doing a significant proportion of the exercises), but the guidance of a course / expert is pretty helpful.

To understand computational complexity, take a course with a title like “theory of computation” or similar. https://en.wikipedia.org/wiki/Computational_complexity_theor...

To understand linear maps, tensor products, etc., take a course (or 2–3 courses) in linear algebra. To understand various matrix decompositions, take a course in numerical linear algebra. https://en.wikipedia.org/wiki/Tensor_product https://en.wikipedia.org/wiki/Cholesky_decomposition

To understand the FFT and convolutions, take a course in signal processing, maybe after a course in ordinary differential equations. https://en.wikipedia.org/wiki/Fast_Fourier_transform https://en.wikipedia.org/wiki/Convolution

To understand the theory of polynomial rings, take a course in abstract algebra. https://en.wikipedia.org/wiki/Polynomial_ring

To understand numerical approximations and error propagation, take a course in numerical analysis. https://en.wikipedia.org/wiki/Numerical_analysis

Courses in discrete math, algorithms, and complex analysis would also be helpful.

Thank you so much! I'll definitely be looking into courses in these subjects. I can learn a language on my own, but theory is something that I personally need someone to help walk me through.

Note that really understanding and grasping all of that can easily take some years, as a full-time student, when you are taking all these courses.

>but the guidance of a course / expert is pretty helpful.

From my peers I get the feeling that this is underappreciated in the tech world where many successful developers skipped college.

> From my peers I get the feeling that this is underappreciated in the tech world where many successful developers skipped college.

I agree that most developers probably underestimate the value of a guidance from a course/expert, and I feel that is largely do to the shear amount of resources available for learning programming.

I have found that as I get into more and more advanced topics the amount of resources available has decreased and has made me want guidance a lot more. Published papers really aren't a great way to learn advanced topics unless you are already an expert in that field.

Mathematics gets hit harder by this than computer science does. I think this is because it is incredibly interconnected and in each topic is very deep; there has been lots of time for the cutting edge to grow.

This is something I really appreciated about some of my well-taught graduate classes (of course, "well-taught" is a big caveat). In undergrad there's often a sense that the professor is supposed to teach you the material. In advanced topics, though, I often found it most useful if the professor actually skipped most of the details, and served as more of a tour guide of the landscape of material for me. Once I know that some specific topic can be learned from a specific tutorial, book chapter, etc., then I can just go learn it on my own. But what's hard is figuring out how to make your way through this sequence entirely DIY, i.e. knowing what to read in what order, whether you're on the right track, where to look if you get stuck, and having someone to answer big-picture questions about how things fit together, why something that seems obvious to me isn't true, etc., etc. I've found some of the best courses helped with that.

A good textbook can also serve this role, but I've found good textbooks rarer than well-taught graduate classes. A lot of textbooks don't really seem to be designed for self-teaching the topic by reading it sequentially cover-to-cover. Maybe because they're often intended to be used in courses, they often have too much material, presented in a somewhat haphazard way, with an expectation that a course instructor will pick and choose parts and supplement it with lectures.

Well it’s two different things. This paper is, in fact, useless in the tech world, since the algorithm is not practical. The paper does, however, has value in advancing academic CS as an intellectual pursuit.

For the very basics, Chapter 30 of Introduction to Algorithms has a very good stand-alone introduction to the topic of large integer multiplication via polynomials and the FFT.

https://en.wikipedia.org/wiki/Introduction_to_Algorithms

Thank you! I'll look into finding a copy soon

Try google :)

Try Library Genesis. :-)

thanks - new to me

I don't know how far you have gotten, but I think it is a good idea to start with FFT-based fast multiplication and read up on whatever unknowns you encounter. In particular I think some abstract algebra (e.g. Dummit-Foote) would be helpful.

There are tons of good expositions on the FFT-way, e.g. check out

"Prime Numbers - A Computational Perspective" by Crandall-Pomerance see ch. 9, Fast algorithms for large-integer arithmetic

If you'd like to see the FFT Multiplication in real-life, practical code implemented / optimized to the hilt, look no further than the GMP library (both source and pre-built binary libs are available).

About the arbitrary precision multiply algorithm:

https://gmplib.org/manual/FFT-Multiplication.html

At large to very large sizes a Fermat style FFT multiplication is used, following Schönhage and Strassen (see References).

Quoted from the GMP web site: https://gmplib.org/

What is GMP?

GMP is a free library for arbitrary precision arithmetic, operating on signed integers, rational numbers, and floating-point numbers. There is no practical limit to the precision except the ones implied by the available memory in the machine GMP runs on. GMP has a rich set of functions, and the functions have a regular interface.

The main target applications for GMP are cryptography applications and research, Internet security applications, algebra systems, computational algebra research, etc.

GMP is carefully designed to be as fast as possible, both for small operands and for huge operands. The speed is achieved by using fullwords as the basic arithmetic type, by using fast algorithms, with highly optimised assembly code for the most common inner loops for a lot of CPUs, and by a general emphasis on speed.

The first GMP release was made in 1991. It is continually developed and maintained, with a new release about once a year.

Since version 6, GMP is distributed under the dual licenses, GNU LGPL v3 and GNU GPL v2. These licenses make the library free to use, share, and improve, and allow you to pass on the result. The GNU licenses give freedoms, but also set firm restrictions on the use with non-free programs.

GMP is part of the GNU project. For more information about the GNU project, please see the official GNU web site.

GMP's main target platforms are Unix-type systems, such as GNU/Linux, Solaris, HP-UX, Mac OS X/Darwin, BSD, AIX, etc. It also is known to work on Windows in both 32-bit and 64-bit mode.

GMP is brought to you by a team listed in the manual.

GMP is carefully developed and maintained, both technically and legally. We of course inspect and test contributed code carefully, but equally importantly we make sure we have the legal right to distribute the contributions, meaning users can safely use GMP. To achieve this, we will ask contributors to sign paperwork where they allow us to distribute their work.

Reply on news.ycombinator.com