beatoriche's blog

Replacing multiple divides to one
By beatoriche, history, 9 years ago, translation, In English

Modern CPUs peform multiplication much faster than division, because of two reasons, multiplications are more considered worthy optimization and are easier to paralellize in silicon. This tells how to replace two divisions with one with small accuracy compomise:

http://stereopsis.com/2div.html

Similarly, you can replace three divisions with one, etc.

  • Vote: I like it
  • +66
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been translated by beatoriche(original revision, translated revision, compare)

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Nice idea...

But I think this will be useful just when we have lots of divides so the program will be slow...But in this situation we can't use any variable to put 1/(a[0]*a[1]*...) in it...(if we want to use just one divide)

So we can just decrease the number of divides(but not to 1)...But does it help in speed a lot?

I'm a beginner and it was just a question...If I'm wrong you can tell me...

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    The proper way to determine is TESTING. It depends on particular compiler and CPU.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ok...

      I did it...

      Test

      I didn't except slower program...But why?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        cout is slow. Printing anything is slow, don't do it when comparing speed of programs.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ok thank you for that point...

          I did it without printing too and just put results in array...

          For N=1e5 not any differences...

          But it was 1s better for N=1e6...(3.95 vs 4.5)

          I know it should have better time but I still think it won't be useful(exactly in CF cause time limits are usually 1s and integer limits are not 1e6 for this problems)

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            It's still useful, even if this only keeps your brain thinking :D

            → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        which type is 'll'? long long? it's for floating point only, unfortunately

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          "ll" is long long but I used "(ld)" in my code...It's long double...

          Ans also in my test without printing I used a "long double" array for result so not any problem...

          → Reply