Linq statement for an infinite sequence of successive halves

Question

Given a starting number, imagine an infinite sequence of its successive halves.

1, 0.5, 0.25, 0.125, ...

(Ignore any numerical instabilities inherent in double.)

Can this be done in a single expression without writing any custom extension methods or generator methods?

Suspensoid

Why the arbitrary restriction? Is this homework? If you're not committed to your expressed limitations, just write an iterator using yield return. – Upturned

Infinite Sequences and Computers do not work together. – Feud

@Ramhound Sure they do, as long as you don't try to get all of the items. – Ninnyhammer

Related: stackoverflow.com/questions/5443939 – Upturned

@hvd: Love it! "You can try, Dr. Turing..." – Unpopular

There is no provided-in-the-standard-sequence-operators method that returns any infinite sequence, and you can't get blood from a stone; without an infinite sequence to start with, you're not going to get an infinite sequence out the back end of any sequence operator. Now, if all you want is a really big sequence, say, with a billion items in it, sure, that's no problem at all. Take Enumerable.Range as large as you like and select i=>x/Math.Pow(2, i) for whatever x is your starting element. – Aquinas

The instabilities in double apply when representing a fraction whose denominator isn't a power of two, or a fraction whose denominator is a power of two but whose numerator requires more than 53 bits to represent. Neither is the case here, so you will get exact representations of all values until you reach double.Epsilon; then all subsequent values will be zero. – Regin

@RobertHarvey, I was just curious to see whether it was possible and hoping to learn something new -- it's been a long time since I had any homework :) As Eric Lippert points out, there are no in-built infinite sequence generation functions, so perhaps there's some kind of trick that'll turn this out. – Suspensoid

@phoog, I didn't know that. Very cool bit of extra info on this question though, thanks. – Suspensoid

@DrewNoakes Yes, I assumed that the starting value was 1, as in the example. An inexact representation of some other fraction, such as 1d/3, will keep the same imprecision (percentage-wise) each time you halve the value (because you're dealing with a power of 2). Division by 2 means decrementing the bits representing the exponent; bits representing the "significand" are unchanged. When you get to denormalized values, division by two is a right bit shift, and you risk losing precision. en.wikipedia.org/wiki/Double-precision_floating-point_format if you're interested in the details. – Regin

Answer 1

I don't know of a single-expression way but I found this clever generator code here: http://csharpindepth.com/articles/Chapter11/StreamingAndIterators.aspx

public static IEnumerable<TSource> Generate<TSource>(TSource start,
                                                  Func<TSource,TSource> step)
{
   TSource current = start;
   while (true)
   {
       yield return current;
       current = step(current);
   }
}

In your case you'd use it:

foreach (double d in Generate<double>(1, c => c / 2))
{
    ...
}

Unpopular

Answer 2

For fun, here's a trick to create a real infinite sequence in a single expression. The first two definitions are class fields, so that they do not require an expression to be initialised.

double? helper;
IEnumerable<double> infinite;

infinite = new object[] { null }.SelectMany(dummy => new double[] { (helper = (helper / 2) ?? 1).Value }.Concat(infinite));

Ninnyhammer

That's great, in a terrible way :) – Suspensoid

I hadn't intended it as anything else :) – Ninnyhammer

Cool. You can enumerate this in LinqPad but for some reason it crashes if you try to do a Count() on it ;o) – Tildie

@hvd Take a look at my answer for another fun solution, it's very much based on yours but using the Y operator. – Lanyard

Answer 3

Here is an answer similar to the one @hvd provided, but using the Y operator defined here, this removes the need for the local variables:

public static Func<A, R> Y<A, R>(Func<Func<A, R>, Func<A, R>> f)
{
    return t => f(Y(f))(t);
}

var halves = Y<double, IEnumerable<double>>(self => d => new[] { 0d }.SelectMany(_ => new[] { d }.Concat(self(d / 2))));

An example use would be:

foreach (var half in halves(20))
    Console.WriteLine(half);

Which would output 20, 10, 5, 2.5 etc...

I wouldn't advise using this in production code but it is fun.

The Y operator also allows other recursive lambda expressions, e.g:

var fibonacci = Y<int, int>(self => n => n > 1 ? self(n - 1) + self(n - 2) : n);
var factorial = Y<int, int>(self => n => n > 1 ? n * self(n - 1) : n);
var hanoi = Y<int, int>(self => n => n == 1 ? 1 : 2 * self(n - 1) + 1);

Lanyard

That's neat. It uses two expressions, but it's just possible that the Y function is already defined somewhere, in which case you could reference that and avoid its definition. – Ninnyhammer

Answer 4

Enumerable.Repeat(1, int.MaxValue).Select((x, i) => x / Math.Pow(2, i))

It isn't actually infinite, but as both Repeat and Select use deferred execution, you won't lose any performance.

Don't know any native way to create infinite linq expression.

Or you can manually write infinite version of .Repeat

Caulis

Answer 5

I don't know of any way to make an infinite sequence with straight LINQ. But you could make a very long sequence.

var sequence = Enumerable.Range(0, int.MaxValue)
                         .Select(n => Math.Pow(2, -n));

However, since double has finite precision, you'll get nothing but zeroes after n gets too high.

Bonkers