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

Groups > comp.arch.embedded > #31301

Re: Definition of an Algorithm

Show all headers | View raw

Rick C <gnuarm.deletethisbit@gmail.com> writes:
> If it has no definite end, it is not an algorithm. ...  If it's not
> deterministic, it's not an algorithm.  Flipping a coin is not an
> algorithm.

There are lots of what are called "randomized algorithms" which involve
flipping coins.  They are used in practice all the time.  An example
might be a Monte Carlo method for computing an integral.  Whether
every problem solvable by a randomized algorithm can be solved equally
efficiently by a non-randomized one is a big unsolved problem in CS
theory, called "P vs BPP".  If you've heard of the more famous P vs NP
problem, it's sort of similar.

There aren't necessarily termination guarantees either.  Tons of
practical cryptography programs somewhere contain a routine to generate,
say, a 100 bit prime number.  The method (that I would informally say
is an algorithm) is:

  1. Generate a random 1000 bit number by flipping coins.
  2. Check whether the resulting number is prime.  (There are known
     deterministic methods for this, but in practice one often uses
     a probabilistic test for this step too).
  3. If yes, you are done.  Otherwise, go back to step 1 and try again.

You can make a good probabilistic estimate of how long the above method
will take, but obviously there is no definite upper bound, since you can
keep generating composite numbers at step 1.

Almost everything in real-world engineering depends on randomness too.
According to statistical thermodynamics, the air molecules in your room
are moving around at random, and there is a small chance that all of
them could coincidentally travel to one small corner of the room.  Your
vacuum cleaner's engineering depends on that not happening, and in
practice it doesn't.  Semiconductors depend on the statistical
properties of charge carriers, and all that.  Randomness is everywhere,
don't be afraid of it.

> How did it return an infinite list?  You mean it returned as many
> digits as you specified or waited to have calculated?

It's a finite data structure that represents an infinite list, just like
a sequence of 32 ones and zeros is a data structure that represents an
integer in a certain range.  In Haskell you can say "x = [1,2..]" and
that means x represents the infinite list 1,2,3,4,5.....  If you try
to print x, you will see 1,2,3,4,5... spewing onto the terminal similar
to if you ran "1 begin dup . 1+ again" in Forth.  More normally you
would say "print (take 5 x)" to print the first 5 elements of x, and
get 1,2,3,4,5.  

> If you have an infinite storage system,

There's no infinite storage system, it's more like a symbolic algebra
system that has a symbol representing the exact number pi.  If you
actually try to print pi, it will start printing 3.14159... using more
and more computation and storage.  But if you say "print cos(pi)", it will
print -1 exactly, that sort of thing.  There's no infinite storage, just
some behind the scenes shortcuts.

Back to comp.arch.embedded | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Definition of an Algorithm Rick C <gnuarm.deletethisbit@gmail.com> - 2022-11-01 20:04 -0700
  Re: Definition of an Algorithm Paul Rubin <no.email@nospam.invalid> - 2022-11-01 22:18 -0700
    Re: Definition of an Algorithm Rick C <gnuarm.deletethisbit@gmail.com> - 2022-11-01 22:42 -0700
      Re: Definition of an Algorithm David Brown <david.brown@hesbynett.no> - 2022-11-02 09:17 +0100
        Re: Definition of an Algorithm Rick C <gnuarm.deletethisbit@gmail.com> - 2022-11-02 11:37 -0700
          Re: Definition of an Algorithm Paul Rubin <no.email@nospam.invalid> - 2022-11-02 15:56 -0700
          Re: Definition of an Algorithm David Brown <david.brown@hesbynett.no> - 2022-11-03 09:56 +0100
          Re: Definition of an Algorithm George Neuner <gneuner2@comcast.net> - 2022-11-03 08:41 -0400
      Re: Definition of an Algorithm Paul Rubin <no.email@nospam.invalid> - 2022-11-02 14:12 -0700
  Re: Definition of an Algorithm David Brown <david.brown@hesbynett.no> - 2022-11-02 09:49 +0100
    Re: Definition of an Algorithm Rick C <gnuarm.deletethisbit@gmail.com> - 2022-11-02 11:45 -0700
      Re: Definition of an Algorithm Dimiter_Popoff <dp@tgi-sci.com> - 2022-11-02 21:29 +0200
        Re: Definition of an Algorithm Rick C <gnuarm.deletethisbit@gmail.com> - 2022-11-02 15:26 -0700
          Re: Definition of an Algorithm David Brown <david.brown@hesbynett.no> - 2022-11-03 10:25 +0100
      Re: Definition of an Algorithm Niklas Holsti <niklas.holsti@tidorum.invalid> - 2022-11-02 21:53 +0200
        Re: Definition of an Algorithm David Brown <david.brown@hesbynett.no> - 2022-11-02 21:53 +0100
        Re: Definition of an Algorithm Rick C <gnuarm.deletethisbit@gmail.com> - 2022-11-02 15:30 -0700
      Re: Definition of an Algorithm David Brown <david.brown@hesbynett.no> - 2022-11-02 22:12 +0100
      Re: Definition of an Algorithm Paul Rubin <no.email@nospam.invalid> - 2022-11-02 14:45 -0700

csiph-web