Angband.oook.cz
Angband.oook.cz
AboutVariantsLadderForumCompetitionComicScreenshotsFunniesLinks

Go Back   Angband Forums > Angband > Development

Reply
 
Thread Tools Display Modes
Old June 21, 2016, 15:59   #11
takkaria
Veteran
 
takkaria's Avatar
 
Join Date: Apr 2007
Posts: 1,936
Donated: $40
takkaria is on a distinguished road
Quote:
Originally Posted by brbrbr View Post
The other issue is more serious, I think.
randint0 return values from 0 to m-1, not from 0 to m.
For example, the "desperate" spell chance calculation
randint0(100) < 50 gives max 99<50, not 100<50
Which is, probably OK, because 0 is also a valid value.
I haven't checked all the code for all randint0 calls, just worried the description is not correct and function may be misused.
z-rand.h says:

randint0: Generates a random signed long integer X where "0 <= X < M" holds.
randint1: Generates a random signed long integer X where "1 <= X <= M" holds.

I think these are accurate, no?
__________________
takkaria whispers something about options. -more-
takkaria is offline   Reply With Quote
Old June 21, 2016, 16:27   #12
brbrbr
Adept
 
Join Date: Sep 2015
Posts: 104
brbrbr is on a distinguished road
Quote:
Originally Posted by takkaria View Post
z-rand.h says:

randint0: Generates a random signed long integer X where "0 <= X < M" holds.
randint1: Generates a random signed long integer X where "1 <= X <= M" holds.

I think these are accurate, no?
No, randint0 generates from 0 to M-1.

So, I've tried to change macro to
Code:
#define randint0(M) ((s32b) Rand_div(M+1))
, recompiled the code, and got heaps of assertion failures.
Angband developers must used it correctly, despite wrong description.
Kudos!

Last edited by brbrbr; June 21, 2016 at 16:35.
brbrbr is offline   Reply With Quote
Old June 21, 2016, 16:37   #13
Derakon
Prophet
 
Derakon's Avatar
 
Join Date: Dec 2009
Posts: 8,942
Derakon is on a distinguished road
Quote:
Originally Posted by brbrbr View Post
No, randint0 generates from 0 to M-1.
To be clear, a generator described as "0 <= X < M" should mean that M cannot be generated, i.e. M-1 is the maximum possible value. Are you saying that in fact M-2 is the maximum possible value? The "max is M-1" case is in fact desirable when picking a random item out of an array; if you tried to access item M then you would get an array index out of bounds exception (if you were working in a modern language, but in C you'd just get an access violation at best and major memory corruption at worst).
Derakon is offline   Reply With Quote
Old June 21, 2016, 23:18   #14
Nick
Vanilla maintainer
 
Nick's Avatar
 
Join Date: Apr 2007
Location: Canberra, Australia
Age: 54
Posts: 7,860
Donated: $60
Nick will become famous soon enough
Quote:
Originally Posted by brbrbr View Post
No, randint0 generates from 0 to M-1.
Which is precisely what "Generates a random signed long integer X where "0 <= X < M" holds." means.

X < M and X, M integers means the greatest value X can take is M-1. Trust me, I'm a mathematician.
__________________
One for the Dark Lord on his dark throne
In the Land of Mordor where the Shadows lie.
Nick is offline   Reply With Quote
Old June 22, 2016, 01:25   #15
brbrbr
Adept
 
Join Date: Sep 2015
Posts: 104
brbrbr is on a distinguished road
Quote:
Originally Posted by Nick View Post
Which is precisely what "Generates a random signed long integer X where "0 <= X < M" holds." means.

X < M and X, M integers means the greatest value X can take is M-1. Trust me, I'm a mathematician.
Ah, point taken. All good here.
brbrbr is offline   Reply With Quote
Old August 16, 2016, 06:22   #16
rhutson
Rookie
 
Join Date: Jul 2013
Location: In the Misty Mountains
Posts: 23
rhutson is on a distinguished road
Quote:
Originally Posted by brbrbr View Post
I am not developer, but very interested:

1) It's year 2016 and the 28 bit mutation remains. Maybe it's time to remove it from z-rand.c as rhutson suggested ????
Feel Freel

Quote:
Originally Posted by brbrbr View Post
The bug means all randint0 generate 1 lower values.
once you have reached the Implementor level.
rhutson is offline   Reply With Quote
Old August 16, 2016, 07:38   #17
rhutson
Rookie
 
Join Date: Jul 2013
Location: In the Misty Mountains
Posts: 23
rhutson is on a distinguished road
Quote:
Originally Posted by AnonymousHero View Post
You're certainly right that using a while loop to do this is absolutely horrible for performance -- not sure why it's done this way (but see below). I'm sure there are much more efficient ways to do it, though I don't know the right search keywords to find an appropriate algorithm on Wikipedia.
The branch is rarely taken in my algorithm. I counted CPU cycles, and I would have never ever injected the inefficient abomination being described into Angband.

Requestfully, [someone] Git the source code, stick in global variables and report the ratio of successful test-branches / function calls. The ratio should be quite, quite low. (I have the source code, but the last time that I played Angband, I started at 6 pm. I had a level 20 character, but I was very sleepy. I looked at the time and wondered why I was so sleepy at only 3 am. Thirty minutes later, I realized that it was 3:30 pm and that I had been playing Angband for 21 1/2 hours. I'm too old for that and don't intend to play Angband again.)

While hardly a reference, the one - but not asserted only- person on this exchange http://stackoverflow.com/questions/1...mber-generator who can be trusted is Rob Napier. Java's implementation seems to me to be the most efficient, while I would say that my algorithm is slightly more efficient for the purposes of Angband than the arc4 algorithm. The performance differences between the 3 algorithms would not even be measurable in microseconds. The primary difference between the 3 algorithms is that I know that I was not paid to design my algorithm.


Quote:
Originally Posted by AnonymousHero View Post
The "while (1)" method doesn't suffer from this bias.

I'm not sure if this actually matters in practice for a game like Angband, but it obviously matters for statistical applications.
Correct. Angband's current RNG implementation does not suffer from any bias.

My motivation for putting my algorithm into the game was so that I could sleep well knowing that tomorrow's prayers and spells would be answered or rejected efficiently and unbiasedly. There is little practical difference between the old fashioned mod % N method versus using an unbiased algorithm. I just couldn't sleep knowing that Angband's RNG was not perfectly unbiased.

Last edited by rhutson; August 16, 2016 at 08:58.
rhutson is offline   Reply With Quote
Old August 16, 2016, 08:50   #18
rhutson
Rookie
 
Join Date: Jul 2013
Location: In the Misty Mountains
Posts: 23
rhutson is on a distinguished road
Quote:
Originally Posted by brbrbr View Post
Ok, that explains why simple modulo was not used
And you now know exactly why a simple modulo was inconsistent with my continued existence.

Quote:
Originally Posted by brbrbr View Post
Now, I have an issue understanding the "Rand_div" code.
For example:
Code:
/* Partition size */
n = (0x10000000 / m);
The usual call for randint is with m=100(decimal), that means the partitions are not of same size, which MAY bias the random number generator.
You seem to me to be an eager student. I would simply share the headerless contents of the email that I sent to Ben explaining how the algorithm works, but I did not maintain a .record in those days. The easiest way for me to explain the algorithm to you would be to use pencil and paper and then scan and upload my diagrams.

Easier for me and as mind food for eager students, read Ben's comments in z-rand.c and then play around with a program that I wrote just today:

Code:
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <assert.h>

uint32_t randit(uint32_t m)
{
    uint32_t n;

    n = (0x10000000 / m);

    return n;
}

int main(int argc, char *argv[])
{
    uint32_t i;

    assert(argc == 2);
    assert((i = atoi(argv[1])) >= 0);
    assert(i <= 0x10000000);

    printf("Part size %u\n", randit(i));
}
Then, please report back your findings! (I do apologize, and no one else would likely relate that my mind is mostly equally focused on the Pros and Cons of Hanging Guitars from a Vaulted Ceiling versus a floorful of guitar stands juxtaposed with the apparent impossiblity of replacing a John Deere lawn mower belt without removing the mower deck.)

Quote:
Originally Posted by brbrbr View Post
It would be much cleaner and faster to use unbiased modulo code:
Code:
#define RAND_MAX=0xFFFFFFFF; 
while(1)
{
  r =  WELLRNG1024a();
  if (r < RAND_MAX - RAND_MAX % m)
    return r % m;
}
That code will run 1 time most of the time. Unbiased.
With parameters of unknown value at compile time, mod is still slightly more expensive than div.

Last edited by rhutson; August 16, 2016 at 11:19.
rhutson is offline   Reply With Quote
Old August 16, 2016, 17:33   #19
AnonymousHero
Veteran
 
AnonymousHero's Avatar
 
Join Date: Jun 2007
Posts: 1,367
AnonymousHero is on a distinguished road
Quote:
Originally Posted by rhutson View Post
(About efficiency of the algorithm.)
Right, I think I originally misread the code, but just never corrected myself.
AnonymousHero is offline   Reply With Quote
Old August 16, 2016, 19:34   #20
rhutson
Rookie
 
Join Date: Jul 2013
Location: In the Misty Mountains
Posts: 23
rhutson is on a distinguished road
Quote:
Originally Posted by AnonymousHero View Post
Right, I think I originally misread the code, but just never corrected myself.
I saw this discussion back in June, but clearly, my attention has been attending to more important matters, hence my delayed response.

There is a Lurking Humor in last night's posts. I was a couple of hours into a detailed study comparing the efficiencies and estimating the CPU cycles used by the 3 algorithms mentioned along with speed testing code, and then I wisely decided to use Nick's approach of "Trust me. I wrote it."

As for the efficiency of my algorithm, I was pleased to discover that it is practically as efficient as reference grade library routines. The algorithm is just more obscure since I was dealing with a different core RNG which was known to produce less than pseudorandom sequences in the lower bits.

As for the 28 bit limitation, that can now be safely and trivially bumped up to a more classic 31 bit limitation. If it is really an issue, email me, and I'll email you back some diffs. But any major rewrite of known working code in such a vital section of the game for no obvious reason would be an ill-advised waste of time.

Last edited by rhutson; August 16, 2016 at 20:11.
rhutson is offline   Reply With Quote
Reply

Tags
rng


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Random map generator. LostTemplar Development 0 May 16, 2013 22:05
Limited Iron Man Mode EpicMan Vanilla 3 December 4, 2010 06:10
Random number generation? Chud Vanilla 21 November 8, 2010 19:00
Mechanic idea for a variant...monster generator Jude Variants 44 November 19, 2008 21:44
Angband Variant without random levels? TJA Variants 32 August 18, 2007 17:47


All times are GMT +1. The time now is 20:43.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, vBulletin Solutions Inc.