Page 2 of 2 FirstFirst 12
Results 41 to 49 of 49

Thread: Using a mathematical identity to speed up certain calculations.

  1. #41

    Thread Starter
    Hyperactive Member Maven's Avatar
    Join Date
    Feb 2003
    Location
    Greeneville, TN
    Posts
    322

    Re: Using a mathematical identity to speed up certain calculations.

    Quote Originally Posted by jemidiah View Post
    The timings you requested, first "GaussLCM", then naive:

    Code:
    In [110]: %timeit sum_quotients5([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43], 100000)
    10 loops, best of 3: 93.9 ms per loop
    
    In [111]: %timeit sum_quotients4([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43], 100000)
    10 loops, best of 3: 131 ms per loop
    I had actually run the first one earlier, and had compared the results to your GaussLCM result in #36, which took 51 ms, hence my "surprisingly close" comments. I'm curious why Python seems so much slower with the Naive method than VB6. I tried a few minor variations and they took essentially the same amount of time as my original.

    That said, I think this type of comparison is mostly an intellectual exercise. I wouldn't use Python in an important, speed-critical application; I'd use Cython or C. The main advantage of Python in this case in my mind is its simplicity, like the naive method being a single line; the fact that gcd, arbitrary-length integers, and more powerful iteration are built-in, no extra debugging or thought needed; and the overall "readability" of the code. I'd say efficiency isn't just a measurement of how fast the code runs; it also includes how long it took to correctly write and how much effort it cost the coder. For solving Project Euler's first problem, I'd say Python wins by a mile on that front: just type "sum(n for n in range(1000) if n%3 == 0 or n%5 == 0)" into an interpreter and you have your answer immediately.
    I don't think one could tell much about comparing times like these. Processes are frequently swapped in and out by the operating system; as a result, one can't tell by looking at the system time how long exactly a process took to complete. Of course, this is outside of computer or operating system comparisons.

    In addition, ask yourself what your trying to optimize for exactly. You're going to get different problems with resulting strategies depending on how you answer the question.
    Education is an admirable thing, but it is well to remember from time to time that nothing that is worth knowing can be taught. - Oscar Wilde

  2. #42
    PowerPoster
    Join Date
    Jun 2013
    Posts
    7,219

    Re: Using a mathematical identity to speed up certain calculations.

    Quote Originally Posted by si_the_geek View Post
    While I don't dispute the change of preference for method based on a different data set, there is obvious bias in your code against the Gauss method.

    In SumNaive you optimise the Ubound call (using the variable UBL), but don't do the equivalent in SumGaussLCM.

    In GCD and SumGaussLCM you do slow integer division (using Int(a / b) etc) rather than the proper method (eg: (a \ b) ).


    There are also other optimisations that could be done for SumGaussLCM (such as a Mod replacement), but the ones I spotted are all things that would take noticeable effort - so it is understandable that you didn't do them for something you only claimed was slightly updated for speed.
    There's no bias against one method or the other - since both are valid algorithms in their own right.
    For certain scenarios one would be choosen over the other.

    Feel free to optimize the GaussLCM-method in my post #38 further if you want,
    but I can tell you that neither the "Ubound-Optimization" will bring any speed-increase -
    nor will any of your suggested "Mod or Div optimizations" work, because those
    are only viable for the (positive) range of VBs Long-Type (Values < 2^31) -
    and for somewhat longer powersets we go far above this range (in the Pow-Variable,
    which is of type Double for a reason).

    I already applied a small optimization in the sub-routine of the GaussLCM (GCD), which
    is the one that takes the most time - where I did:
    ...If a < 2147483647# Then h = a Mod b ...
    but applying a likewise optimization in other places is not worthwhile, because the
    inner-loop within the (already changed to non-recursive) GCD-function is the most
    frequented piece of code.

    So your allegation that I was biased is unfounded - you didn't even checked
    the changes you suggested out on your own...

    In the same style as in the other discussions we had already, you engage in
    speculation, applying only half-knowledge - not posting any code.
    I hope I am allowed to say that much - and that you don't try to ban me again,
    for the sole reason of pointing out your imprecise and kind of insulting behaviour.

    Remember that we are in Code-It-Better here - if you think that you can speed
    up the last SumGaussLCM by factor 2 or 3, then by all means don't talk that much -
    just do it and post the code and the results of your native compiled binary.
    *Then* call me biased (after delivering proof).

    And no, other than you wrote further above that:
    "there are also other optimisations that could be done for SumGaussLCM (such as a Mod replacement)"
    there is no such thing in the GaussLCM-routine - there's only the GCD-Sub-Routine which
    contains a Modulo-Op (already optimized for Values where this is possible) ...
    whilst the SumGaussLCM itself contains only "faked Integer-Divs" (no Modulo-Ops at all).

    So, what remains is your Ubound-suggestion - well, here is the updated code which contains that:

    Code:
    Option Explicit
    
    Private Declare Function timeGetTime Lib "winmm" () As Long
    Private Declare Function timeBeginPeriod Lib "winmm" (ByVal uPeriod As Long) As Long
    
    Private Sub Form_Load()
      timeBeginPeriod 1
      AutoRedraw = True
      Caption = "Click the Form..."
    End Sub
    
    Function LongArr(ParamArray P()) As Long()
    Dim i As Long, L() As Long
      ReDim L(UBound(P))
      For i = 0 To UBound(P): L(i) = P(i): Next
      LongArr = L
    End Function
    
    Private Sub Form_Click()
    Dim n As Long, PrimeFactorList() As Long, i As Long, T As Long, Result As Currency
       Cls
       
       n = 100000
       Print vbLf; "n ="; n; vbLf
    
       Print "Result for Factors(174, 192, 934, 554, 1234, 4321)"
       PrimeFactorList = LongArr(174, 192, 934, 554, 1234, 4321)
       T = timeGetTime
         For i = 1 To 500: Result = SumNaive(n, PrimeFactorList): Next
       Print "Naive", Result, Format((timeGetTime - T) / 500, "0.000msec")
       T = timeGetTime
         For i = 1 To 500: Result = SumGaussLCM(n, PrimeFactorList): Next
       Print "GaussLCM", Result, Format((timeGetTime - T) / 500, "0.000msec"); vbLf
     
       Print "Result for Primes (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43)"
       PrimeFactorList = LongArr(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43)
       T = timeGetTime
         For i = 1 To 10: Result = SumNaive(n, PrimeFactorList): Next
       Print "Naive", Result, Format((timeGetTime - T) / 10, "0.0msec")
       T = timeGetTime
         For i = 1 To 10: Result = SumGaussLCM(n, PrimeFactorList): Next
       Print "GaussLCM", Result, Format((timeGetTime - T) / 10, "0.0msec"); vbLf
       
       Print "Result for Primes (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71)"
       PrimeFactorList = LongArr(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71)
       T = timeGetTime
         For i = 1 To 3: Result = SumNaive(n, PrimeFactorList): Next
       Print "Naive", Result, Format((timeGetTime - T) / 3, "0.0msec")
       T = timeGetTime
         For i = 1 To 3: Result = SumGaussLCM(n, PrimeFactorList): Next
       Print "GaussLCM", Result, Format((timeGetTime - T) / 3, "0.0msec"); vbLf
    End Sub
     
    Private Function SumNaive(ByVal n As Long, L() As Long) As Double
    Dim i As Long, j As Long, UBL As Long
      UBL = UBound(L)
      For i = 1 To n
        For j = 0 To UBL
          If i Mod L(j) = 0 Then SumNaive = SumNaive + i: Exit For
      Next j, i
    End Function
     
    Private Function SumGaussLCM(ByVal n As Long, L() As Long) As Double
    Dim i As Long, j As Long, s As Double, Pow As Double, ni As Long, UBL As Long
    Static P2(0 To 30) As Long: If P2(0) = 0 Then For i = 0 To 30: P2(i) = 2 ^ i: Next
     
      UBL = UBound(L)
      For i = 1 To P2(UBL + 1) - 1
        Pow = 1
        s = -0.5
        For j = 0 To UBL
          If i And P2(j) Then s = -s: Pow = Int(Pow * L(j) / GCD(Pow, L(j)))
        Next j
        ni = Int(n / Pow)
        SumGaussLCM = SumGaussLCM + s * Pow * ni * (ni + 1)
      Next i
    End Function
    
    'used in SumGaussLCM only, to calculate the least-common-multiple there
    Private Function GCD(ByVal a As Double, ByVal b As Long) As Double
    Dim h As Long
      Do While b > 0
        If a < 2147483647# Then h = a Mod b Else h = a - b * Int(a / b)
        a = b: b = h
      Loop
      GCD = a
    End Function
    And as you see, no changes speedwise when you compare the results for the already posted sets from #38:
    http://www.vbforums.com/images/ieimages/2014/07/1.png

    ...with these new ones:
    http://vbRichClient.com/Downloads/GaussSumOpt2.png

    And the best argument against your allegation that I was disfavouring the GaussLCM deliberately,
    is the last set in the above screen-shot- which was only increased by 6 additional Primes, but causing
    a disadvantage of the GaussLCM of about factor *500* now.

    With my earlier, shorter lists, I tried to point out, from what amount of Primes in the list,
    (roughly - and for n=100000) the GaussLCM is at a disadvantage with native VB6-code.
    But there *exists* such a Balance-point (as already mentioned in post #25) -
    and no factor 2 or even a factor 10 faster GaussLCM would help much, since the
    performance of this algo *will* get worse (with the Factors-Count of the list) exponentially.


    Olaf
    Last edited by Schmidt; Jul 2nd, 2014 at 09:36 PM.

  3. #43
    Super Moderator si_the_geek's Avatar
    Join Date
    Jul 2002
    Location
    Bristol, UK
    Posts
    41,929

    Re: Using a mathematical identity to speed up certain calculations.

    Quote Originally Posted by Schmidt View Post
    There's no bias against one method or the other - since both are valid algorithms in their own right.
    Both being valid clearly does not mean they are of equal quality. If you wrote one and a beginner wrote the other, we would expect the quality of yours to be better.

    In the context of a speed trial, it is unquestionable (but not necessarily intentional) bias to have a speed optimisation only in one, when it can clearly be applied to both. That applies whether or not the effect turns out to be noticeable.

    Your admission of only having "slightly updated for speed" clearly implies that there will probably be a speed bias towards the simpler one (as that is much easier to optimise). As I said before that is absolutely fine (because you made the caveat), but later claiming there is no bias at all is blatantly dishonest.

    but I can tell you that neither the "Ubound-Optimization" will bring any speed-increase -
    nor will any of your suggested "Mod or Div optimizations" work, because those
    are only viable for the (positive) range of VBs Long-Type (Values < 2^31)
    Regarding the UBound optimisation, you thought it was worth adding to the other method, so it was wrong to not also apply it in the same way to the Gauss one.

    While I made a mistake regarding the range of the \ operator in VB6, a Mod replacement clearly does not need to have the same limits as the built-in Mod operator.

    In the same style as in the other discussions we had already, you engage in
    speculation, applying only half-knowledge - not posting any code.
    My one mistake does not mean speculation or half-knowledge. It is childish for you to make up that kind of insult about people just because they point out some of the flaws in your posts.

    As for the comment regarding code, you are well aware that these days the majority of my forum time needs to be moderation, rather than code based.

    Stop the trolling and lies - as evidenced in that quote and several other places in your post, and openly admitted by you on multiple occasions in the past.

    I hope I am allowed to say that much - and that you don't try to ban me again,
    for the sole reason of pointing out your imprecise and kind of insulting behaviour.
    That is slanderous.

    As you are well aware, people only get banned for violating the rules - and in the case of your previous ban the violation was unquestionably fully intentional (as were the multiple times before that when you were only warned).

  4. #44
    PowerPoster
    Join Date
    Jun 2013
    Posts
    7,219

    Re: Using a mathematical identity to speed up certain calculations.

    Quote Originally Posted by si_the_geek View Post
    Both being valid clearly does not mean they are of equal quality.
    All of the algos I've posted had the same quality (apparently the one Olaf Schmidt
    was able to come up with).

    In my very first version-pair they had "Schmidt-non-Optimized quality" -
    and after posting the optimized versions, they both had "Schmidt-Optimized quality".

    To the best of my abilities - in the timeframe which lay between posting the unoptimized
    version till I came up with the optimized one.

    Quote Originally Posted by si_the_geek View Post
    If you wrote one and a beginner wrote the other, we would expect the quality of yours to be better.
    Doesn't apply here, since I wrote both pairs of algos myself.

    So what do you want to imply here really?

    Quote Originally Posted by si_the_geek View Post
    In the context of a speed trial, it is unquestionable (but not necessarily intentional) bias to have a speed optimisation only in one, when it can clearly be applied to both.
    That applies whether or not the effect turns out to be noticeable.
    You mean I'm under the obligation, to apply optimizations only *you-think* are
    worthwhile (as your Ubound-suggestion for the Gauss), even when *I know*
    that the optimization has no effect, and only clutters the code unnecessarily?

    Quote Originally Posted by si_the_geek View Post
    Your admission of only having "slightly updated for speed" clearly implies that there
    will probably be a speed bias towards the simpler one (as that is much easier to optimise).
    Again, what do you want to imply here - that I didn't do my best in the small timeframe
    until I posted the optimized versions?

    For me "bias" implies *intent* (as in deliberately leaving easy to apply optimizations out
    in one of the algos, to "fake results").

    If there was no intent on my part - then where is the "bias"?

    And if there are easy to apply optimizations for the Gauss - which one should I have
    implemented?

    The Ubound-Optimization clearly is not worthwhile for the Gauss, since it only brings
    one pro-mille (if even that) - so I left it out.

    Quote Originally Posted by si_the_geek View Post
    ...but later claiming there is no bias at all is blatantly dishonest.
    So now I'm even "dishonest" for posting well-performing algos into the Code-It-Better-Forum?

    Do you have no shame?

    First I have to swallow the allegation, that I didn't do my best -
    and when "speaking up in defense", I'm now labeled a liar.

    Fine, just great - perhaps the reason we're getting along that fine.

    Quote Originally Posted by si_the_geek View Post
    Regarding the UBound optimisation, you thought it was worth adding to the other method,
    so it was wrong to not also apply it in the same way to the Gauss one.
    A good example for what I mean with "speculation and half-knowledge" on your part.

    I *knew* that it wouldn't bring any speedups in the Gauss (because I *tested* it) - whereas you *guessed*.

    Quote Originally Posted by si_the_geek View Post
    While I made a mistake regarding the range of the \ operator in VB6, a Mod replacement clearly does not need to have the same limits as the built-in Mod operator.
    I already wrote, that I implemented a replacement for the Mod-Operation in the GCD-routine,
    it's sitting right in front of you when you look at the code - if you have a better idea how
    to implement a faster Mod (which doesn't choke above the range of the Long-Type) - this
    is the Code-It-Better-forum. I found my Mod-replacement a sufficient one, since it *did*
    speed things up for the Gauss-algo.

    Quote Originally Posted by si_the_geek View Post
    My one mistake does not mean speculation or half-knowledge.
    You didn't know about the timing-per-call of VBs-Ubound-Operation (I did, because I tested it) -
    so your recommendation was based on "half-knowledge and speculation".

    You didn't know about the increase in value of the Pow-Variable (I did, because I tested it) -
    and so wrongly suggested to use the Integer-Operators on a Double - so your recommendation
    was based on "half-knowlege and speculation".

    You wrote about "optimizing Mod-Operations" within the GaussLCM - there's only one Mod-
    Operation - and it's not in the GaussLCM-, but in the GCD-routine - and it *is* already an
    optimized version of the "classic, integerbased" Modulo-Op.

    Quote Originally Posted by si_the_geek View Post
    It is childish for you to make up that kind of insult about people just because they point out some of the flaws in your posts.
    Ok, now I'm even called "childish" for telling the truth - and BTW, could you clearly
    point out, which "flaws in my posts" you're talking about?

    I'd be interested in knowing about them.

    Quote Originally Posted by si_the_geek View Post
    As for the comment regarding code, you are well aware that these days the majority of my forum time needs to be moderation, rather than code based.
    If you don't have the time to make postings with your "developer-hat on", then why posting
    comments you cannot back-up, when others point out the flaws in them.

    Speculation (not testing things out before posting) is not really helpful - you're clearly
    wasting your time doing that.

    Quote Originally Posted by si_the_geek View Post
    Stop the trolling and lies...
    Ok - now you even mark my posts as not only lying to others -
    but my speaking up in defense as trolling.

    Quote Originally Posted by si_the_geek View Post
    As you are well aware, people only get banned for violating the rules - and in the case of your previous ban the violation was unquestionably fully intentional (as were the multiple times before that when you were only warned).
    Si, "all the other posts" you're talking about were happening (and starting) *exactly* as this current
    dialogue *here* (which may serve as just another example, should this lead to a ban of me again).

    I was simply *disagreeing-with-you* - the post which led to my ban was for disagreeing about
    DoEvents (where I - as always - was backing up my claims with *code* - whereas you were
    not doing anything in this regard - just continuing with claims which were already disproven).

    You werer wrong there (in my opinion - though backed up with code) - and you are wrong here
    (again - in my opinion - though backed up with hard proof by code too).

    When will you start to simply prove the things wrong, for which I called you "engaging in speculation"?
    - You speculated about Ubound being worthwhile in the GaussLCM (I posted already
    code and timings, which clearly proved that this is not the case)

    - You speculated about Integer Divs being worthwhile (whilst not being aware in what range
    the Values came in).

    - You speculated about "a faster Modulo Op" (which could have been applied in my optimization) -
    whereas the code clearly shows, that I already have one in place... again - why not
    simply post code which does it better?

    It would really be topping it should I get banned for these ridiculous things again...
    By the same moderator - and for the same reason of "simple offended pride".


    Olaf
    Last edited by Schmidt; Jul 3rd, 2014 at 09:30 PM.

  5. #45
    Super Moderator si_the_geek's Avatar
    Join Date
    Jul 2002
    Location
    Bristol, UK
    Posts
    41,929

    Re: Using a mathematical identity to speed up certain calculations.

    Quote Originally Posted by Schmidt View Post
    All of the algos I've posted had the same quality (apparently the one Olaf Schmidt
    was able to come up with).
    Just because the same person wrote them clearly does not mean they have the same quality.

    For me "bias" implies *intent* (as in deliberately leaving easy to apply optimizations out
    in one of the algos, to "fake results").
    That is intentionally taking things the wrong way to cause an argument, aka Trolling.

    So now I'm even "dishonest" for posting well-performing algos into the Code-It-Better-Forum?
    Trolling again (you were dishonest for your claims, not your code).

    There are several instances of that kind of behaviour in your post, and it is not acceptable.

    If you want to play those kinds of games, do it on another site.

    I already wrote, that I implemented a replacement for the Mod-Operation in the GCD-routine,
    it's sitting right in front of you when you look at the code - if you have a better idea how
    to implement a faster Mod (which doesn't choke above the range of the Long-Type) - this
    is the Code-It-Better-forum. I found my Mod-replacement a sufficient one, since it *did*
    speed things up for the Gauss-algo.
    While it may speed things up, there are much better versions available (including on this site). It wouldn't take long for you to find one if you thought it worthwhile to look at them.

    As you have once again decided to respond to constructive criticism (pointing out things that could be improved, and hinting at how) with large amounts trolling and other distraction methods, I now have less time to spare, so I'm not going to waste time helping you further.

    Si, "all the other posts" you're talking about were happening (and starting) *exactly* as this current
    dialogue *here*
    Yes - me posting in a reasonable manner, and you responding with various forms of uncivilised behaviour, despite knowing that is not acceptable here.

    I was simply *disagreeing-with-you* - the post which led to my ban was for disagreeing about
    DoEvents (where I - as always - was backing up my claims with *code* - whereas you were
    not doing anything in this regard - just continuing with claims which were already disproven).
    Most of that is totally untrue - for example, you are fully aware that you were banned for intentionally violating a rule after being explicitly warned about it.

    It would really be topping it should I get banned for these ridiculous things again...
    By the same moderator - and for the same reason of "simple offended pride".
    My pride isn't offended, but you are approaching a ban - because you are still refusing to act in a manner that is appropriate for this site.

    The site isn't going to change, so as multiple admins and moderators (and many other members) have warned you before, you need to act in an appropriate manner for this site if you want to stay here.


    Now lets get this back to the important matter - sensible discussion of the original topic.

  6. #46
    Only Slightly Obsessive jemidiah's Avatar
    Join Date
    Apr 2002
    Posts
    2,431

    Re: Using a mathematical identity to speed up certain calculations.

    Since the original topic is likely dead (after having been derailed twice, and having relatively little content to begin with), I'll make a few "meta" comments.

    Boy, this was a painful thread to participate in. Schmidt's interactions with si and Maven both got very personal very quickly. He managed to make everyone else (including me, a little) defensive after one reply each. Frankly Schmidt, you need to learn to play well with others. Having good ideas is not enough--having amazingly great ideas might be, but I haven't seen that from you so far. I'm reminded of an intern a friend of mine worked with. He had implemented some odd sorting algorithm, and during code review was told to change it to something standard. Instead, he wrote a proof of correctness of his original algorithm in the comments. Unsurprisingly, he was not hired after the internship. I don't know if the particulars of this example are applicable to you Schmidt, but the general idea certainly is: coding is about more than just telling a computer how to do things; having productive interactions with others is fundamentally important.

    On the flip side, Maven and si could have done better to not let Schmidt get under their skin. Just focus on the content; if you start writing something that depends on your character/skills or the character/skills of the other person, you should probably just delete it and let it go. For instance, I had started to reply to Schmidt's "650" comment above, saying something to the effect of, "I can divide 130 ms by 199 µs, thank you very much," but am glad I didn't actually post it, since it's just not helpful. (I'm sorry it ended up in this post, though it's a good example.) (I understand si's role as a moderator is different from my role as a random forum user. si and Schmidt's exchange seems almost entirely unhelpful regardless.)

    With all the bickering and nitpicking and talking past each other, this thread is *way* longer than it should have been, and I doubt it will help many people code anything better, if only because of the sheer amount of personal "spew" you have to wade through to get at the content.

    Anywho, best of luck everyone; no hard feelings; have a good life if I don't see you again.
    The time you enjoy wasting is not wasted time.
    Bertrand Russell

    <- Remember to rate posts you find helpful.

  7. #47
    Angel of Code Niya's Avatar
    Join Date
    Nov 2011
    Posts
    8,598

    Re: Using a mathematical identity to speed up certain calculations.

    Any thread with Si+Schmidt or me+axisdj+Carlos Rocha+Schmidt or dilettante+any MS fan is going to have some kind of drama. Donno what it is about these combination of personalities but it never ends well lol....
    Treeview with NodeAdded/NodesRemoved events | BlinkLabel control | Calculate Permutations | Object Enums | ComboBox with centered items | .Net Internals article(not mine) | Wizard Control | Understanding Multi-Threading | Simple file compression | Demon Arena

    Copy/move files using Windows Shell | I'm not wanted

    C++ programmers will dismiss you as a cretinous simpleton for your inability to keep track of pointers chained 6 levels deep and Java programmers will pillory you for buying into the evils of Microsoft. Meanwhile C# programmers will get paid just a little bit more than you for writing exactly the same code and VB6 programmers will continue to whitter on about "footprints". - FunkyDexter

    There's just no reason to use garbage like InputBox. - jmcilhinney

    The threads I start are Niya and Olaf free zones. No arguing about the benefits of VB6 over .NET here please. Happiness must reign. - yereverluvinuncleber

  8. #48

    Thread Starter
    Hyperactive Member Maven's Avatar
    Join Date
    Feb 2003
    Location
    Greeneville, TN
    Posts
    322

    Re: Using a mathematical identity to speed up certain calculations.

    Quote Originally Posted by jemidiah View Post
    Since the original topic is likely dead (after having been derailed twice, and having relatively little content to begin with), I'll make a few "meta" comments.

    Boy, this was a painful thread to participate in. Schmidt's interactions with si and Maven both got very personal very quickly. He managed to make everyone else (including me, a little) defensive after one reply each. Frankly Schmidt, you need to learn to play well with others. Having good ideas is not enough--having amazingly great ideas might be, but I haven't seen that from you so far. I'm reminded of an intern a friend of mine worked with. He had implemented some odd sorting algorithm, and during code review was told to change it to something standard. Instead, he wrote a proof of correctness of his original algorithm in the comments. Unsurprisingly, he was not hired after the internship. I don't know if the particulars of this example are applicable to you Schmidt, but the general idea certainly is: coding is about more than just telling a computer how to do things; having productive interactions with others is fundamentally important.

    On the flip side, Maven and si could have done better to not let Schmidt get under their skin. Just focus on the content; if you start writing something that depends on your character/skills or the character/skills of the other person, you should probably just delete it and let it go. For instance, I had started to reply to Schmidt's "650" comment above, saying something to the effect of, "I can divide 130 ms by 199 µs, thank you very much," but am glad I didn't actually post it, since it's just not helpful. (I'm sorry it ended up in this post, though it's a good example.) (I understand si's role as a moderator is different from my role as a random forum user. si and Schmidt's exchange seems almost entirely unhelpful regardless.)

    With all the bickering and nitpicking and talking past each other, this thread is *way* longer than it should have been, and I doubt it will help many people code anything better, if only because of the sheer amount of personal "spew" you have to wade through to get at the content.

    Anywho, best of luck everyone; no hard feelings; have a good life if I don't see you again.

    I can only blame myself since I made the post without proof reading or checking the formula. The main point to the topic was that mathematical identities are useful for speeding up certain calculations on computers. An observation that nobody seems to have made is that both algorithms come from the same identity. The left hand side of the identity was the basis for the algorithm posted by Schmidt. There is nothing interesting about the approach; instead, it was obvious. In mathematics, there are countless identities for various problems. When one faces a calculation, it's wroth while to check to see if an identity is readily available. Some identities can save many orders of magnitude of algorithmic complexity. For example, the right hand identity found by Guass saved us one order of complexity.

    I would like to point out that there is a difference between code optimization and algorithmic optimization. I think people tend to confuse the two. In code optimization, the goal is to get an algorithm to run faster on a specific machine. Outside of embedded systems, code optimization is mostly a waste of time. Algorithmic optimization is about reducing complexity of an algorithm. I don't mean complexity in the sense that the algorithm is easier to understand; instead, I mean complexity in terms of the number of steps required to solve a problem. For example, a selection sort has a worse case of O(n^2). If we're talking about sorting an array, the steps required to do it using a selection sort is the size of the array squared. The heap sort on the other hand has a O(nlogn) complexity. Again n here is referring to the size of the array. So the heap sort has a lower complexity than the selection sort even though the heap sort is more difficult to understand than the selection sort.

    So to bring this back to the above, mathematical identities can be useful to get lower complexity on many mathematical problems. They are superior to code optimization of higher complexity algorithms because not performing steps is faster than performing highly optimized steps.

    This ties into many arguments about languages. What is the fastest language etc. Algorithms are generally more important than language selection. One can optimize an O(n^2) algorithm in assembly code and bring the algorithm to its maximum potential on a machine; however, we could implement an algorithm with a lower complexity of o(n) in visual basic and run circles around the highly tuned o(n^2) algorithm written in assembler.
    Education is an admirable thing, but it is well to remember from time to time that nothing that is worth knowing can be taught. - Oscar Wilde

  9. #49
    Super Moderator si_the_geek's Avatar
    Join Date
    Jul 2002
    Location
    Bristol, UK
    Posts
    41,929

    Re: Using a mathematical identity to speed up certain calculations.

    I would disagree with the level of benefit from language chosen and code optimisation, because in the right cases they can each make a massive speed difference, and in many others they give a worthwhile benefit (which is often enough).

    I do agree however that the algorithm is the best place to start - because it is usually by far the biggest differentiator (and often takes less effort), plus it often alters the other two phases.

Page 2 of 2 FirstFirst 12

Posting Permissions

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



Click Here to Expand Forum to Full Width