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

Groups > comp.arch.embedded > #31296

Re: Definition of an Algorithm

Show all headers | View raw

On 2022-11-02 20:45, Rick C wrote:
> On Wednesday, November 2, 2022 at 4:49:26 AM UTC-4, David Brown wrote:

    [snip]


>> I remember a programming task from my days at university (doing
>> mathematics and computation), writing a function that calculated the
>> digits of pi. The language in question was a functional programming
>> language similar to Haskell. The end result was a function that
>> returned an infinite list - you could then print out as many digits from
>> that list as you wanted.
> 
> How did it return an infinite list?


Probably by using a non-strict evaluation order 
(https://en.wikipedia.org/wiki/Evaluation_strategy#Non-strict_evaluation) 
where a data object can be "unbounded" or "potentially infinite" -- only 
the parts of the data structure that are later accessed become "real" 
data held in memory.

You could of course say that the part (function) of the program that 
produced the potentially infinite list is not an "algorithm" by itself, 
and becomes an algorithm only when combined with the part of the program 
that outputs a finite part of the list. But that seems too limited, 
because it that function is clearly independent of the rest of the 
program and implements a well-defined computation.


>> Was it "deterministic" ? Not all algorithms are deterministic and
>> repeatable, but it is often a very useful characteristic, and it might
>> have been relevant for the course you were doing at the time.
> 
> If it's not deterministic, it's not an algorithm.  Flipping a coin is
> not an algorithm.

Randomized or probabilistic algorithms are a huge research subject with 
many practical applications, for example for the approximate solution of 
hard optimization problems 
(https://en.wikipedia.org/wiki/Randomized_algorithm).

A very simple example is the "random sample consensus" method (RanSaC), 
which is often called an "algorithm" although it is not deterministic 
(https://en.wikipedia.org/wiki/Random_sample_consensus).

Back to comp.arch.embedded | Previous | Next — Previous in thread | Next 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