Results 1 to 6 of 6

Thread: Multiplication via vectorized tables; several times faster than normal?

  1. #1
    Member JamesWasil's Avatar
    Join Date
    Dec 2017
    Location
    Arizona
    Posts
    65
    Thanks
    70
    Thanked 13 Times in 12 Posts

    Lightbulb Multiplication via vectorized tables; several times faster than normal?

    Here is the paper for it as PDF which has 2 different methods proposed to achieve this:
    Integer Multiplication In Time O (n log n)
    https://hal.archives-ouvertes.fr/hal-02070778/document

  2. Thanks:

    Shelwien (20th October 2019)

  3. #2
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,775
    Thanks
    276
    Thanked 1,206 Times in 671 Posts
    Nice, but misleading; its about multiplication of long numbers rather than common integers used in programming.
    Also O(n*log(n)) complexity is defined for Turing machines, who knows how it would compare to cpu instructions,
    and what's the minimum n where it becomes useful.

  4. #3
    Member
    Join Date
    Apr 2012
    Location
    Stuttgart
    Posts
    448
    Thanks
    1
    Thanked 101 Times in 61 Posts
    Quote Originally Posted by Shelwien View Post
    Nice, but misleading; its about multiplication of long numbers rather than common integers used in programming. Also O(n*log(n)) complexity is defined for Turing machines, who knows how it would compare to cpu instructions, and what's the minimum n where it becomes useful.
    Probably an old trick. There is an analysis of long multiplication in Knuth, "The Art of Programming", Vol.2. The observation is that multiplication of long numbers has some commonalities with convolution, and thus a multiplication can be replaced by a fourier transformation, a digit-wise multiplication, and a backwards transformation. Fourier is O(n*log(n)), thus multiplication can be done in the same complexity. I'm not sure whether there was an analysis of practiability, but if the numbers are "long enough", it will pay. Just unclear what "long enough" is.

  5. Thanks:

    JamesWasil (21st October 2019)

  6. #4
    Programmer schnaader's Avatar
    Join Date
    May 2008
    Location
    Hessen, Germany
    Posts
    593
    Thanks
    233
    Thanked 228 Times in 108 Posts
    Quote Originally Posted by thorfdbg View Post
    Probably an old trick. There is an analysis of long multiplication in Knuth, "The Art of Programming", Vol.2. The observation is that multiplication of long numbers has some commonalities with convolution, and thus a multiplication can be replaced by a fourier transformation, a digit-wise multiplication, and a backwards transformation. Fourier is O(n*log(n)), thus multiplication can be done in the same complexity. I'm not sure whether there was an analysis of practiability, but if the numbers are "long enough", it will pay. Just unclear what "long enough" is.
    This is known as the Schönhage-Strassen algorithm - and "long enough" seems to be somewhere above 10,000 decimal digits:

    In practice the Schönhage–Strassen algorithm starts to outperform older methods such as Karatsuba and Toom–Cook multiplication for numbers beyond 2^(2^15) to 2^(2^17) (10,000 to 40,000 decimal) digits.The GNU Multi-Precision Library uses it for values of at least 1728 to 7808 64-bit words (33,000 to 150,000 decimal digits), depending on architecture. There is a Java implementation of Schönhage–Strassen which uses it above 74,000 decimal digits.
    Also, it has an upper bound of O(n * log n * log log n) - worse than O(n * log n) - and is mentioned in the paper, so there seems to be an improvement indeed.
    http://schnaader.info
    Damn kids. They're all alike.

  7. Thanks:

    JamesWasil (21st October 2019)

  8. #5
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,775
    Thanks
    276
    Thanked 1,206 Times in 671 Posts
    I wonder if its possible to apply some of these optimizations to numeral system conversion.
    For example, I recently made this: https://encode.su/threads/3122-dec2b...on-digits-file
    and it has long multiplications... but *base is O(N)... but *base^(N/k) might be "long enough" and would allow to create k threads.
    So then, I wonder if this can be applied to entropy coding?

  9. Thanks:

    JamesWasil (21st October 2019)

  10. #6
    Member JamesWasil's Avatar
    Join Date
    Dec 2017
    Location
    Arizona
    Posts
    65
    Thanks
    70
    Thanked 13 Times in 12 Posts
    Quote Originally Posted by Shelwien View Post
    I wonder if its possible to apply some of these optimizations to numeral system conversion.
    For example, I recently made this: https://encode.su/threads/3122-dec2b...on-digits-file
    and it has long multiplications... but *base is O(N)... but *base^(N/k) might be "long enough" and would allow to create k threads.
    So then, I wonder if this can be applied to entropy coding?
    I was thinking yes, and that characteristics from this approach could be beneficial for your encoders and others who want to speed up multiplication.

    If you find that not all sequences are large enough or uniform to use it, it could still be used as a hybrid multiplier.

    E.g: If a number or sequence is in a certain range of digits where you know it will be safe to use a table, you can utilize the faster algorithm that does the multiplication in its place. If it is a shorter sequence than the safe range, then normal multiplication would be used. It wouldn't speed up everything, but with error checking (or range analysis) and switching between the two, you could alternate between them and possibly make multiplication faster to improve encoding times.

Similar Threads

  1. Counting byte freq., could this be vectorized?
    By anormal in forum The Off-Topic Lounge
    Replies: 14
    Last Post: 25th August 2018, 21:54
  2. Faster compression or faster decompression
    By cassini in forum Data Compression
    Replies: 7
    Last Post: 27th September 2016, 08:50
  3. the zero redunduncy in zpaq normal jpg compression
    By toi007 in forum Data Compression
    Replies: 3
    Last Post: 16th August 2012, 23:40
  4. Vectorized rangecoder
    By Shelwien in forum Data Compression
    Replies: 5
    Last Post: 16th January 2011, 18:32
  5. decompression is ~1000 times slower than compression?
    By Alexander Rhatushnyak in forum Data Compression
    Replies: 17
    Last Post: 28th April 2010, 13:27

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •