6 ms·

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

by burk96 8y ago

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?

jacobolus 8y ago
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_theory 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/Tensor_product https://en.wikipedia.org/wiki/Cholesky_decomposition 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/Fast_Fourier_transform https://en.wikipedia.org/wiki/Convolution 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 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 https://en.wikipedia.org/wiki/Numerical_analysis Courses in discrete math, algorithms, and complex analysis would also be helpful.
- fromthestart 8y ago
  >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.
  - umanwizard 8y ago
    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.
  - thethirdone 8y ago
    > 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.
    - _delirium 8y ago
      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.
- burk96 8y ago
  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.
  - albertzeyer 8y ago
    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.
jpz 8y ago
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 https://en.wikipedia.org/wiki/Introduction_to_Algorithms
- burk96 8y ago
  Thank you! I'll look into finding a copy soon
  - jpz 8y ago
    Try google :)
    - wolfgke 8y ago
      Try Library Genesis. :-)
      - jpz 8y ago
        thanks - new to me
kurlberg 8y ago
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
rhw168 8y ago
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 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/ 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.

by burk96 8y ago

jacobolus 8y ago

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_theory 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/Tensor_product https://en.wikipedia.org/wiki/Cholesky_decomposition 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/Fast_Fourier_transform https://en.wikipedia.org/wiki/Convolution 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 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 https://en.wikipedia.org/wiki/Numerical_analysis Courses in discrete math, algorithms, and complex analysis would also be helpful.

fromthestart 8y ago
>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.
- umanwizard 8y ago
  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.
- thethirdone 8y ago
  > 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.
  - _delirium 8y ago
    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.
burk96 8y ago
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.
- albertzeyer 8y ago
  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.

jpz 8y ago

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 https://en.wikipedia.org/wiki/Introduction_to_Algorithms

burk96 8y ago
Thank you! I'll look into finding a copy soon
- jpz 8y ago
  Try google :)
  - wolfgke 8y ago
    Try Library Genesis. :-)
    - jpz 8y ago
      thanks - new to me

kurlberg 8y ago

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

rhw168 8y ago

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 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/ 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.