BigInteger, Range, Stream, and iterators


#1

I am playing with factorial (to play with data-driven testing in Kotlin) and, of course, BigInteger is the only sensible type to be using for this. For the classical iterative implementation you might thing of:

fun iterative(x:BigInteger):BigInteger {

  validate(x)

  var total = one

  for (i in two..x) { total *= i }

  return total

}

(one is BigInteger.ONE and two is BigInteger.valueOf(2).) This however fails because the expression two..x delivers an object that does not have an iterator method. Hopefully I am just missing something rather than it being a bug.

An alternative might be:

fun iterative(x:BigInteger):BigInteger {
  validate(x)
  var total = one
  (two..x).forEach{i -> total *= i}
  return total
}

Sadly this fails because the compiler is unable to do type inference. This implies that (two…x) is not a Something<BigInteger> which seems weird as it really ought to be.

Adding the extra type information:

fun iterative(x:BigInteger):BigInteger {
  validate(x)
  var total = one
  (two..x).forEach{(i:BigInteger) -> total *= i}
  return total
}

But this fails because an appropriate forEach cannot be found because (two…x) is not Stream<BigInteger>.

Am I just missing something blindingly obvious?


#2

The standard library doesn't implement ranges or progressions for BigInteger. I threw together some BigInteger sugar here:

http://kotlin-demo.jetbrains.com/?publicLink=61203304-132683114

If you include that stuff in your project then what you want to do should work. Something like that should probably be in the standard library, though I’m not sure I understand why you think factorial requires BigInteger in this case. 64 bits is a lot!


#3

Sponditious. Excellent, new, shiny stuff :-)

Thanks for this, I shall work on it tomorrow.

As for BigInteger rather than Long, try calculating factorial(30) and avoiding arithmetic overflow. 64-bit binary number MAX really is quite a small value.


#4

Mike,

Well that works for me most splendidly.  :-)

What’s the process for getting something of equivalent functionality into the standard Kotlin distribution?


#5

It's open source, so just open a pull request. I don't bother because the last few pull requests I opened are all either closed or stuck in limbo - JetBrains likes to do things in their way and to a schedule that often isn't published.

If you want to try your luck go right ahead though, I don’t mind. The code is licensed however it needs to be for inclusion. I suspect you’d need to change the bigint extension property to a method called toBigInteger() for consistency with the existing API though, even though it’s quite verbose.


#6

I wonder if the:

  0.bigint, 1.bigint

or whatever property name is consistent with current Kotlin, is not so good an idea, and that providing:

  zeroBig, zeroOne,…

is a better one. Properties cause the constructor to be run every time with no memoization, provideing precomputed immutable values seems likely to lead to more efficient code?

I have transformed your little test into the beginning of a TestNG test, so I may evolve the code and then present it to the pull request system.


#7

No. The code I gave you calls BigInteger.valueOf(Long) which internally does memoize. Read the source and you'll see.


#8

I suspect the code needs an update for Kotlin 1.0.0-rc. The tinkerings I have done all end up with an error of one sort or another :frowning:


#9

Certainly, BigInteger makes sense as the return type for Factorial, but not for the input to factorial. Factorial of Long.MAX_VALUE will probably take years to calculate and I doubt the answer will even fit into memory. So it seems kind of silly to allow for bigger inputs than that.


#10

From a pragmatic view I have no doubt that any actual call to Factorial in any real code will use an argument 0 ≤ n ≤ 2⁶⁴ and so a Long would do fine as the parameter. Moreover using Γ (Gamma Function), or Stirling’s Formula would likely be useful to speed things up compared to the algorithms in use here. However this code is about BigInteger being a first class integral type in Kotlin, as it is in Groovy and Ceylon, not about implementations of Factorial. So to remove the BigInteger parameters would be to run away from the real problem as far as Kotlin is concerned.

The other main purpose of this, and the Fibonacci Sequence examples, is testing, and property-based testing rather than example-based testing. The repository contains many implementations in any languages to exercise idiomatic testing in the various languages so as to compare attitudes to testing for this sort of code.


#11

You are falsely assuming that when someone responds to one statement you made that implies something about the other statements you made.

But since you seem to want a statement about the rest of it, I will respond. You think that Range should also support being a progression and I would say no it shouldn’t because I don’t think there is any real call for any sequence longer than 2^63 values. And considering that each value generated creates an object, I wouldn’t lose any sleep over it.


#12

On the other hand, by creating a BigIntegerRange without any thought of being related to Progression, but which provides the features anyway, you end up with a perfectly functioning code. Factorial with BigInteger arguments working again. Fibonacci codes suffering a code generation problem :frowning:

Moral of story: Just do it.