UBigInt

[zhelenskiy]

I suppose that there are many areas (e. g. cryptography) where BigInt can be only non-negative. That makes me think that it would be great to introduce semiring (or maybe semifield) UBigInt. It has an extra advantage: it can ve inlined as it would have only UIntArray field.

A question appears: we can choose between

• Copying each time to remove the leading zeroes
• Storing actual length in the first cell

The second is better because it is cheaper than copying, but worse because it has some indirection.

There is actually the Magnitude typealias to UIntArray and there are functions given for additions, multiplication, etc. So we can make a normal public @JvmInline type that can and should be possible to use in external projects that use kmath.

[altavir]

I think that the Magnitude is the implementation detail, it should be hidden. As for BigInt, I have no objections to UBigInt, but it would be nice to have some actual use-cases. Also performance considerations are not clear here, since the benefit seems negligible.

[zhelenskiy]

I want to replace Magnitude with UBigInt, not to make Magnitude public. It would be great to have dual type as Long + ULong, Int + UInt, Short + UShort, Byte + UByte. In cryptography you usually don't need negative values. Also, if I want to make some big indexes (my own case), I want them to be non-negative. It would be great if I could guarantee that with type system. Especially, because BigInt is based on Magnitude that is de facto almost the thing I want.

In slack you (correct me if I am wrong) suggested to avoid inderection and store sign of BigInt inside Magnitude to avoid inderection. So I pointed that here as we don't need to store sign and can store poor inlined magnitude. However, that is still an additional point for, but not the main one.

[altavir]

Something like this?

@JvmInline value class UBigInt(val array: UIntArray)

It looks good. We can actually do a common context for them. ensure that plus operation on to UBigInt returns UBigInt but other operations return BigInt. I like that.

[zhelenskiy]

That is actually what I was speaking about.

The next thought is that now we have generic BigInt with sign -1 normally and 1 when we didn't know it before. Then we can also create NegativeBigInt ( < 0) and we can create sealed interface BigInteger with abstract mehods that return BigInteger. However, implementation may specify the type (Negative + negative = negative, etc). We can let it be

@JvmInline
value class NegativeBigInt(absoluteValue: UBigInt)

This can help us to

• Avoid existence of 2 implementations of positive integers as both UBigInts and generic BigInts;
• Use as construction to specify if we are sure about the output type in runtime;
• Inline sign using types (with no overhead when possible).

[zhelenskiy]

To remove problems of 0 (-UInt != Negative as -0 = 0) I suggest to make Zero a separate object.

[zhelenskiy]

However, then I have no type that starts with 0. So I suggest to make UBigInt an intermediate between BigInt and Positive + zero.

sealed interface BigInt {
    operator fun plus(other: Bigint)
    val absoluteValue: UBigInt
}

@JvmInline
value class NegativeBigInt(val opposite: PostiveBigInt) {
    override fun toString() = "-$absoluteValue"
    override operator fun plus(other: BigInteger): BigInteger = when (other) {
        is ... -> plus(other)
        ...
    }
    operator fun plus(other: NegativeBigInt): NegativeBigInt
    ...
    override val absoluteValue get() = opposite.asUBigInt()
}

@JvmInline
value class PositiveBigInt(private val array: UIntArray) {
    fun asUBigInt() = UBigInt(this)
}

@JvmInline
value class UBigInt (val value: PositiveBigInt? /* Null when zero */) : BigInt {
    fun asPositive() = value
    override val absoluteValue get() = this
}

[zhelenskiy]

Another way to do it is to make UBigInt not a BigInt:

sealed interface BigInt {
    operator fun plus(other: Bigint)
    val absoluteValue: UBigInt
    operator fun unaryMinus(): BigInteger
    
}

inline fun BigInt.toUBigIntOrThrow() = ...
inline fun BigInt.toUBigIntOrNull() = ...

@JvmInline
value class NegativeBigInt(val oppositeValue: PostiveBigInt) {
    override fun toString() = "-$absoluteValue"
    override operator fun plus(other: BigInteger): BigInteger = when (other) {
        is ... -> plus(other)
        ...
    }
    operator fun plus(other: NegativeBigInt): NegativeBigInt
    ...
    override val absoluteValue get() = oppositeValue.asUBigInt()
    override operator fun unaryMinus(): PositiveBigInt = absoluteValue
}

@JvmInline
value class PositiveBigInt(private val array: UIntArray) : BigInt {
    init {
        require(array.isNotEmpty()) { "Magnitude is not empty for non-zero numbers" }
        require(array.last()) { "Leading zeroes are forbidden" }
    }
    override operator fun unaryMinus(): NegativeBigInt = NegativeBigInt(this)
}

fun PositiveBigInt.toBigInt() = UBigInt(this)

object Zero : BigInt { ... }

fun Zero.toUBigInt() = UBigInt(null)

@JvmInline
value class UBigInt (val value: PositiveBigInt? /* Null when zero */) /* no : BigInt*/ {
    fun asPositive() = value
    override val absoluteValue get() = this
    fun toBigInt() = value ?: Zero
}

[zhelenskiy]

The second one has an advantage that if user needs some other combination of positives, zero and negatives but UBigInt (positives and zero), he can create one and it would have the same place in the class hierarchy that UBigInt has.

[zhelenskiy]

We need semialgebras, semirings, semifields, etc. to support positive bigints.

[zhelenskiy]

The second approach is here: https://github.com/zhelenskiy/BigIntProto/tree/master/src/commonMain/kotlin

It became quite awful because of introducing UBigInt that is alien to the hierarchy of BigInts (PositiveBigInt <: BigInt, but not PositiveBigInt <: UBigInt <: BigInt). So choosing a return type is usually a challenge there.

So I'll try to implement the first suggestion. Arguing with its disadvantages (listed above): I can admit that other combinations of positives zeroes and negatives are useless in real life so that is not a real problem that the hierarchy problem would appear in non-existing cases. The Zero problem would be solved by the assertion that the opposite of the negative number is not zero.

[zhelenskiy]

I tried it and it is a lot more convenient: https://github.com/zhelenskiy/BigIntProto/tree/alt-master/src/commonMain/kotlin.

[altavir]

An interesting approach. I do not think that NBigInt will be used though. Also storing a sign as a class discriminator could significantly impact performance (especially on JS).

What I had in mind after the discussion is to use UBigInt and create a separate algebra for it (implementing semi-ring). And then create a BigInt as a wrapper around it. It is necessary to include semi-ring in the main hierarchy of algebras, but I also do not see any strong arguments not to do so.

[zhelenskiy]

Do you mean that it is better stil not to make it store sign explicitly and not to make UBigInt : BigInt?

[zhelenskiy]

Another problem, I actually see, is

I cannot override equals for value classes.