7

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?

Drew Noakes
  • 300,895
  • 165
  • 679
  • 742
  • 4
    Why the arbitrary restriction? Is this homework? If you're not committed to your expressed limitations, just write an iterator using `yield` `return`. – Robert Harvey Feb 22 '12 at 17:21
  • 5
    Infinite Sequences and Computers do not work together. – Security Hound Feb 22 '12 at 17:23
  • 7
    @Ramhound Sure they do, as long as you don't try to get all of the items. –  Feb 22 '12 at 17:25
  • Related: http://stackoverflow.com/questions/5443939 – Robert Harvey Feb 22 '12 at 17:26
  • @hvd: Love it! "You can try, Dr. Turing..." – n8wrl Feb 22 '12 at 17:29
  • 7
    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. – Eric Lippert Feb 22 '12 at 17:34
  • 4
    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. – phoog Feb 22 '12 at 17:34
  • 1
    @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. – Drew Noakes Feb 22 '12 at 18:39
  • @phoog, I didn't know that. Very cool bit of extra info on this question though, thanks. – Drew Noakes Feb 22 '12 at 18:39
  • 1
    @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. http://en.wikipedia.org/wiki/Double-precision_floating-point_format if you're interested in the details. – phoog Feb 22 '12 at 18:49

5 Answers5

11

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))
{
    ...
}
n8wrl
  • 19,439
  • 4
  • 63
  • 103
10

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));
4

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);
Lukazoid
  • 19,016
  • 3
  • 62
  • 85
  • 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. –  Feb 23 '12 at 08:28
2
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

Drew Noakes
  • 300,895
  • 165
  • 679
  • 742
Archeg
  • 8,364
  • 7
  • 43
  • 90
1

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.

Justin Morgan - On strike
  • 30,035
  • 12
  • 80
  • 104