Skip to content

randint() implementation is flawed #2024

@goualard-f

Description

@goualard-f

Describe the bug

The randint() function in the Calculation module uses a flawed algorithm that can make it return values outside the requested domain. This can happen in two ways:
1/ When providing bounds that lead to an integer overflow;
2/ When the underlying floating-point RNG returns 1.0f (in the Random::random<float> implementation, there are 128 integers out of 2^{32} that can give that result ---approx. 1 in 3e8).

Relying on Random::random<float> also entails that randint() cannot ensure uniformity: Ion::random() generates
integers in [0,2^{32}-1] with a uniform distribution. Once divided by 0xffffffff, some floating-point numbers are created more frequently than others due to rounding (See https://hal.science/hal-02427338). This translates to some integers returned more often than others with randint().

Proposed cure: change the algorithm used entirely (see, e.g., Lemire's nearly divisionless algorithm: https://lemire.me/blog/2019/06/06/nearly-divisionless-random-integer-generation-on-various-systems/).

Screenshots

screenshot

To Reproduce

Steps to reproduce the behavior:

  1. Go to the 'Calculation' app
  2. Type 'randint(0,2^31-1)'
  3. See error

This is the way to reproduce the first problem. The second problem, linked to the floating-point RNG cannot easily be reproduced with either the device or the simulator, since it requires calling randint() an unknown number of times.

Expected behavior

A clear and concise description of what you expected to happen.

randint(a,b) should return an integer in [a,b], not outside of it.

Environment

  • Epsilon version (Settings > About > Software version).
    20.4.0
  • The platform(s) on which the problem happens: online simulator, actual device, etc...
    Online simulator and actual device.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions