Petr's blog

A return@week

By Petr, history, 6 months ago, In English

https://blog.mitrichev.ch/2024/05/a-returnweek.html

  • Vote: I like it
  • +34
  • Vote: I do not like it

»
6 months ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

Thanks for the mention!

Regarding the comments about the ModInt class: I experimented with it and found it is slightly slower (even with inline class) than the global infix functions, and I find it annoying to convert between ModInt, Int and Long. I also like the fact that by using a global "mp" I am more explicit about which operations are modded or not.

The decision to stick to "mp" was made a long time ago (since I am orange ish). I know many others have used ModInt class and found success, so I would not be surprised if I end up switching to using ModInt later.

→ Reply
  • »
    »
    6 months ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    Thanks for sharing! According to this comment and other sources in the internet, it's impossible in Kotlin for code like "val == 0" to work when val is ModInt, so ModInt will come with its own caveats...

    → Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it 
    @JvmInline
@Suppress("NOTHING_TO_INLINE")
private value class ModInt(val x: Int) {
    inline operator fun plus(other: ModInt) = ModInt((x + other.x).let { if (it >= MOD) it - MOD else it })
    inline operator fun minus(other: ModInt) = ModInt((x - other.x).let { if (it < 0) it + MOD else it })
    inline operator fun times(other: ModInt) = ModInt((x.toLong() * other.x % MOD).toInt())
    fun power(p_: Int): ModInt {
        var a = this
        var res = ModInt(1)
        var p = p_
        while (p != 0) {
            if ((p and 1) == 1) res *= a
            a *= a
            p = p shr 1
        }
        return res
    }

    inline operator fun div(other: ModInt) = this * other.inv()
    inline fun inv() = power(MOD - 2)

    companion object {
        inline fun from(x: Int) = ModInt((x % MOD + MOD) % MOD)
        inline fun from(x: Long) = ModInt(((x % MOD).toInt() + MOD) % MOD)
    }
}

@JvmInline
private value class ModIntArray(private val storage:IntArray) {
    operator fun get(index: Int) = ModInt(storage[index])
    operator fun set(index: Int, value: ModInt) { storage[index] = value.x }
    val size get() = storage.size
}
private inline fun ModIntArray(n: Int, init: (Int) -> ModInt) = ModIntArray(IntArray(n) { init(it).x })

    Didn't have performance problems with it. But, can agree, it's not very handy to cast/work with constants.

    → Reply