Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #55724

Re: www.equestionanswers.com - C,C++, VC++,MFC,COM,DCOM, DLL question and answers for interviews and self-study

Show all headers | View raw

bert <bert.hutchings@btinternet.com> writes:
> On Monday, 29 December 2014 09:57:56 UTC, Ike Naar  wrote:
> > On 2014-12-29, Dr Nick <nospam-4@temporary-address.org.uk> wrote:
> > > It's not as though anyone has recently
> > > discovered a better algorithm or anything.
> > 
> > Euclid discovered a better algorithm (but not recently).
> 
> Stein's algorithm avoids divisions, except by 2.

Euclid's algorithm didn't have any divisions to avoid.

> One of the web 
> pages about it dates it from 1967, but admits that it might be 
> quite a lot older.  It does have similarities to the "Russian 
> peasant" method of multiplication.

Indeed, Stein was published in 67, but I think he discovered it in
1961. I don't really see the similarity between with the Russian
peasant method (although perhaps I've only seen an abstraction of that
method which has removed the similarity).

Whilst Stein's is genuinely a different algorithm from Euclid's,
rather than merely an optimisation (unlike the division-based
optimisation of Euclid, which essentially dates back to Lehmer in the
30s), it's still not a huge leap from the original.

Sorensen tweaked Stein in the 90s. In simplest possible terms, 
Sorensen : Stein :: Lehmer : Euclid.

Knuth and Schoenhage approached the problem in different fields
(and by which, I don't mean "fields", which have no GCD) which
don't necessarily easily apply to the integer problem way back
in the early 70s.

The only method for integers that is significantly different from
the original, IMHO, is Stehle and Zimmerman's, but in essense
this is just wringing the maximum from Sorensen's improvements
of Stein's (taking it to 'divide and conquer' levels, rather
than just chipping away bits).

Phil, who realised that in his previous post, his "linear"
comment was assuming a computational model where add/shift/etc.
take constant time on any size input. (Such as a modern PC with
fixed size arithmetic types - which was the model we were in,
so it wasn't such a guff. In Big-Oh-land, such ops are linear,
so Euclid is quadratic.)
-- 
The best part of re-inventing the wheel is that you get to pick how
many sides the new one has. -- egcagrac0 on SoylentNews

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

www.equestionanswers.com - C,C++, VC++,MFC,COM,DCOM, DLL question and answers for interviews and self-study EQuestionAnswers Inc <equestionanswers@gmail.com> - 2014-12-27 22:41 -0800
  Re: www.equestionanswers.com - C,C++, VC++,MFC,COM,DCOM, DLL question and answers for interviews and self-study Barry Schwarz <schwarzb@dqel.com> - 2014-12-28 10:02 -0800
    Re: www.equestionanswers.com - C,C++, VC++,MFC,COM,DCOM, DLL question and answers for interviews and self-study Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-12-28 19:55 +0000
      Re: www.equestionanswers.com - C,C++, VC++,MFC,COM,DCOM, DLL question and answers for interviews and self-study bert <bert.hutchings@btinternet.com> - 2014-12-28 12:41 -0800
        Re: www.equestionanswers.com - C,C++, VC++,MFC,COM,DCOM, DLL question and answers for interviews and self-study Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-12-28 20:47 +0000
          Re: www.equestionanswers.com - C,C++, VC++,MFC,COM,DCOM, DLL question and answers for interviews and self-study BartC <bc@freeuk.com> - 2014-12-28 21:48 +0000
            Re: www.equestionanswers.com - C,C++, VC++,MFC,COM,DCOM, DLL question and answers for interviews and self-study Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-12-29 00:57 +0000
            Re: www.equestionanswers.com - C,C++, VC++,MFC,COM,DCOM, DLL question and answers for interviews and self-study Phil Carmody <pc+usenet@asdf.org> - 2015-01-03 15:08 +0200
              Re: www.equestionanswers.com - C,C++, VC++,MFC,COM,DCOM, DLL question and answers for interviews and self-study BartC <bc@freeuk.com> - 2015-01-03 13:31 +0000
                Re: www.equestionanswers.com - C,C++, VC++,MFC,COM,DCOM, DLL question and answers for interviews and self-study Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-01-03 15:13 +0000
                Re: www.equestionanswers.com - C,C++, VC++,MFC,COM,DCOM, DLL question and answers for interviews and self-study BartC <bc@freeuk.com> - 2015-01-03 21:23 +0000
      Re: www.equestionanswers.com - C,C++, VC++,MFC,COM,DCOM, DLL question and answers for interviews and self-study Dr Nick <nospam-4@temporary-address.org.uk> - 2014-12-29 09:45 +0000
        Re: www.equestionanswers.com - C,C++, VC++,MFC,COM,DCOM, DLL question and answers for interviews and self-study Ike Naar <ike@iceland.freeshell.org> - 2014-12-29 09:57 +0000
          Re: www.equestionanswers.com - C,C++, VC++,MFC,COM,DCOM, DLL question and answers for interviews and self-study bert <bert.hutchings@btinternet.com> - 2014-12-29 04:07 -0800
            Re: www.equestionanswers.com - C,C++, VC++,MFC,COM,DCOM, DLL question and answers for interviews and self-study Phil Carmody <pc+usenet@asdf.org> - 2015-01-03 15:43 +0200
    Re: www.equestionanswers.com - C,C++, VC++,MFC,COM,DCOM, DLL question and answers for interviews and self-study Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-01-03 13:57 +0000
      Re: www.equestionanswers.com - C,C++, VC++,MFC,COM,DCOM, DLL question and answers for interviews and self-study Greg Martin <greg.at.softsprocket@dot.com> - 2015-01-03 19:46 +0000

csiph-web