View Issue Details

IDProjectCategoryView StatusLast Update
0000802LDMud 3.5Implementationpublic2018-01-30 04:59
Reporterzesstra Assigned ToGnomi  
PrioritynormalSeverityminorReproducibilityalways
Status resolvedResolutionfixed 
Platformx86_64OSMacOS XOS Version10.6.x
Target Version3.5.0Fixed in Version3.5.0 
Summary0000802: Lower 11 bits missing for 64 bit wide random numbers
DescriptionThe result of random(__INT_MAX__) on LP64 platforms has only 53 random bits, the lower 11 bits are always 0. One effect is, that all these numbers are even.
The reason is that we intermediately convert the result of the PRNG to double, which has only a precision of 53 bits, so the rest get lost.

The simplest way is to use long double intermediately, but this does not work with all platforms/compilers (e.g. MS VC++ uses long double as synonym for double).
TagsNo tags attached.

Relationships

child of 0000555 closed Complete support for 64bit (LP64) architectures 

Activities

zesstra

2012-12-08 21:52

administrator   ~0002171

Ok, I had a look into two possibilities to fix this:

1) Use the scaling method with intermediate floats. This needs long double, which are less portable.
2) Since the MT has a quite good distribution, we might get away with just using plain modulo. This would be more portable.

I will attach a comparison between the current state and the two alternatives. The spreadsheet contains some raw data for equally long bitstreams generated by random(2^n) and three graphs comparing the bits of entropy per bit, the Chi^2 and the serial correlation factor.
Based on that I think the difference in quality between both approaches is not to great.
What do you think?

Gnomi

2012-12-28 09:49

manager   ~0002180

Last edited: 2012-12-28 09:49

Or we could do integer arithmetic, this function does rand * n >> BITS, assuming that rand has BITS number of random bits:

p_uint scale(p_uint rand, p_uint n)
{
#define BITS (sizeof(p_int)*8)
#define HBITS (BITS/2)
#define HMASK ((1<<HBITS) - 1)

    p_uint rand_h = rand >> HBITS;
    p_uint rand_l = rand & HMASK;

    p_uint n_h = n >> HBITS;
    p_uint n_l = n & HMASK;

    p_uint result_h = rand_h * n_h;
    p_uint result_l = rand_h * n_l;

    result_h += result_l >> HBITS;
    result_l &= HMASK;
    result_l += rand_l * n_h;
    result_h += result_l >> HBITS;
    result_l &= HMASK;
    result_l += (rand_l * n_l) >> HBITS;
    result_h += result_l >> HBITS;

    return result_h;
}

Gnomi

2015-05-10 22:44

manager  

mult.c (1,362 bytes)   
#include <stdio.h>
#include <inttypes.h>

typedef int32_t p_int;
typedef uint32_t p_uint;

p_uint scale(p_uint rand, p_uint n)
{
#define BITS (sizeof(p_int)*8)
#define HBITS (BITS/2)
#define HMASK ((1<<HBITS) - 1)

    p_uint rand_h = rand >> HBITS;
    p_uint rand_l = rand & HMASK;

    p_uint n_h = n >> HBITS;
    p_uint n_l = n & HMASK;
    
    p_uint result_h = rand_h * n_h;
    p_uint result_l = rand_h * n_l;
    
    result_h += result_l >> HBITS;
    result_l &= HMASK;
    result_l += rand_l * n_h;
    result_h += result_l >> HBITS;
    result_l &= HMASK;
    result_l += (rand_l * n_l) >> HBITS;
    result_h += result_l >> HBITS;

    return result_h;
}

void check(uint32_t rand, uint32_t n)
{
    uint32_t result1 = scale(rand, n);
    uint32_t result2 = (uint32_t)((((uint64_t) rand) * ((uint64_t) n)) >> 32);
    
    printf("%s %08X x %08X = %08X, %08X\n", result1 == result2 ? " " : "!", rand, n, result1, result2);
}

int main()
{
    check(1,1);
    check(0x7FFFFFFF,2);
    check(0x80000000,2);
    check(2,0x7FFFFFFF);
    check(2,0x80000000);
    check(0xFFFFFFFF,10);
    check(10,0xFFFFFFFF);
    check(0xFFFF0000,0xFFFF0000);
    check(0x0000FFFF,0xFFFF0000);
    check(0xFFFF0000,0x0000FFFF);
    check(0x0000FFFF,0x0000FFFF);
    check(0xFFFF0000,0x00010000);
    check(0x0000FFFF,0x00010000);
    check(0xFFFFFFFF,0xFFFFFFFF);
}
mult.c (1,362 bytes)   

zesstra

2018-01-28 22:31

administrator   ~0002294

Fix committed in revision 82f7fccf36d8e5767384750adce3a004d78f878c to master branch (see changeset 1143 for details). Thank you for reporting!

Gnomi

2018-01-29 19:59

manager   ~0002301

Fix committed in revision 82f7fccf36d8e5767384750adce3a004d78f878c to master branch (see changeset 1207 for details). Thank you for reporting!

Gnomi

2018-01-29 20:34

manager   ~0002347

Fix committed in revision 82f7fccf36d8e5767384750adce3a004d78f878c to master branch (see changeset 2408 for details). Thank you for reporting!

Gnomi

2018-01-29 22:57

manager   ~0002352

Fix committed in revision 82f7fccf36d8e5767384750adce3a004d78f878c to master branch (see changeset 2530 for details). Thank you for reporting!

Gnomi

2018-01-30 04:59

manager   ~0002403

Fix committed in revision 82f7fccf36d8e5767384750adce3a004d78f878c to master branch (see changeset 2409 for details). Thank you for reporting!

Issue History

Date Modified Username Field Change
2012-02-17 22:49 zesstra New Issue
2012-12-08 21:52 zesstra Note Added: 0002171
2012-12-08 21:52 zesstra Assigned To => zesstra
2012-12-08 21:52 zesstra Status new => assigned
2012-12-08 21:53 zesstra File Added: Zufallsvergleich.ods
2012-12-08 21:56 zesstra Relationship added child of 0000555
2012-12-28 09:49 Gnomi Note Added: 0002180
2012-12-28 09:49 Gnomi Note Edited: 0002180
2015-04-29 21:18 zesstra Project LDMud 3.3 => LDMud 3.5
2015-04-29 21:19 zesstra Product Version 3.3.720 =>
2015-04-29 21:19 zesstra Target Version 3.3.721 => 3.5.0
2015-05-10 22:44 Gnomi File Added: mult.c
2015-05-10 22:44 Gnomi File Deleted: Zufallsvergleich.ods
2017-04-26 23:23 Gnomi Assigned To zesstra => Gnomi
2017-09-30 18:03 Gnomi Status assigned => resolved
2017-09-30 18:03 Gnomi Resolution open => fixed
2017-09-30 18:03 Gnomi Fixed in Version => 3.5.0
2018-01-28 22:31 Source_changeset_attached => ldmud.git master 82f7fccf
2018-01-28 22:31 zesstra Note Added: 0002294
2018-01-29 19:59 Gnomi Source_changeset_attached => ldmud.git master 82f7fccf
2018-01-29 19:59 Gnomi Note Added: 0002301
2018-01-29 20:34 Gnomi Source_changeset_attached => ldmud.git master 82f7fccf
2018-01-29 20:34 Gnomi Note Added: 0002347
2018-01-29 22:57 Gnomi Source_changeset_attached => ldmud.git master 82f7fccf
2018-01-29 22:57 Gnomi Note Added: 0002352
2018-01-30 04:59 Gnomi Source_changeset_attached => ldmud.git master 82f7fccf
2018-01-30 04:59 Gnomi Note Added: 0002403