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

Groups > comp.arch.embedded > #31298

Re: Definition of an Algorithm

Show all headers | View raw

On 02/11/2022 20:53, Niklas Holsti wrote:
> 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.
> 

The more relevant term is "lazy evaluation".  It is very common in 
functional programming languages, and allows you to work with infinite 
lists, infinite mutually recursive functions, and all kinds of fun.

> 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.
> 

The function returns a function as part of the output.

> 
>>> 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).
> 

All sorts of algorithms are non-deterministic.  Pretty much any 
algorithm that is executed in parallel parts is going to have 
non-deterministic execution, which can result in non-deterministic outputs.

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