Re: jot(1) changed behavior
On Sat, Jul 16, 2016 at 09:46:29PM +0200, Theo Buehler wrote:
> I see two options apart from reverting my commit.
>
> 1. Just fix the bug Otto noticed. Remove the section on randomness
>completely and fix one example in the manual. That's what the patch
>in this mail does. The patch for jot.c is the same as in my previous
>mail.
>
> 2. Restore the previous behavior when -w or -c is specified together
>with -r and fix the bug Otto noticed. I will send this patch in a
>second mail.
>
> sobrado@ and I checked that this patch would match the behavior of Linux
> and NetBSD. In particular, the format string does not change the output
> drastically:
>
> $ jot -r 10 1 3 | sort -n | uniq -c
> 33148 1
> 33452 2
> 33400 3
> $ jot -w %d -r 10 1 3 | sort -n | uniq -c
> 33373 1
> 33239 2
> 33388 3
>
> I think this behavior makes sense: if the output consists of integers
> anyway, then a %d format should not alter it, independently of what
> happens under the hood.
>
> The downside is that it breaks scripts that relied on the previous
> behavior that was explicitly mentioned in the manual (as Philippe found
> the hard way; sorry about that!).
>
i know we need to tread carefully with breaking scripts, but i think the
balance is that we need a sane world too. i think we should take the stand
for simplicity and sanity (option 1).
ok for the man page.
jmc
> Index: jot.1
> ===
> RCS file: /var/cvs/src/usr.bin/jot/jot.1,v
> retrieving revision 1.19
> diff -u -p -r1.19 jot.1
> --- jot.1 4 Jan 2016 23:21:28 - 1.19
> +++ jot.1 16 Jul 2016 19:09:59 -
> @@ -225,41 +225,6 @@ specifying an integer format:
> .Bd -literal -offset indent
> $ jot -w %d 6 1 10 0.5
> .Ed
> -.Pp
> -For random sequences, the output format also influences the range
> -and distribution of the generated numbers:
> -.Bd -literal -offset indent
> -$ jot -r 10 1 3 | sort -n | uniq -c
> -24950 1
> -50038 2
> -25012 3
> -.Ed
> -.Pp
> -The values at the beginning and end of the interval
> -are generated less frequently than the other values.
> -There are several ways to solve this problem and generate evenly distributed
> -integers:
> -.Bd -literal -offset indent
> -$ jot -r -p 0 10 0.5 3.5 | sort -n | uniq -c
> -33374 1
> -33363 2
> -33263 3
> -
> -$ jot -w %d -r 10 1 4 | sort -n | uniq -c
> -33306 1
> -33473 2
> -33221 3
> -.Ed
> -.Pp
> -Note that with random sequences, all numbers generated will
> -be smaller than the upper bound.
> -The largest value generated will be a tiny bit smaller than
> -the upper bound.
> -For floating point formats, the value is rounded as described
> -before being printed.
> -For integer formats, the highest value printed will be one less
> -than the requested upper bound, because the generated value will
> -be truncated.
> .Sh EXAMPLES
> Print 21 evenly spaced numbers increasing from \-1 to 1:
> .Pp
> @@ -280,7 +245,7 @@ comes after the character
> .Sq z
> in the ASCII character set):
> .Pp
> -.Dl "$ jot \-r \-c 160 a { | rs \-g0 0 8"
> +.Dl "$ jot \-r \-c 160 a z | rs \-g0 0 8"
> .Pp
> Infinitely many
> .Xr yes 1 Ns 's
> Index: jot.c
> ===
> RCS file: /var/cvs/src/usr.bin/jot/jot.c,v
> retrieving revision 1.27
> diff -u -p -r1.27 jot.c
> --- jot.c 10 Jan 2016 01:15:52 - 1.27
> +++ jot.c 16 Jul 2016 19:10:18 -
> @@ -277,9 +277,6 @@ main(int argc, char *argv[])
> if (prec > 9) /* pow(10, prec) > UINT32_MAX */
> errx(1, "requested precision too large");
>
> - while (prec-- > 0)
> - pow10 *= 10;
> -
> if (ender < begin) {
> x = begin;
> begin = ender;
> @@ -287,16 +284,22 @@ main(int argc, char *argv[])
> }
> x = ender - begin;
>
> - /*
> - * If pow10 * (ender - begin) is an integer, use
> - * arc4random_uniform().
> - */
> - use_unif = fmod(pow10 * (ender - begin), 1) == 0;
> - if (use_unif) {
> - uintx = pow10 * (ender - begin);
> - if (uintx >= UINT32_MAX)
> - errx(1, "requested range too large");
> - uintx++;
> + if (prec == 0 && (fmod(ender, 1) != 0 || fmod(begin, 1) != 0))
> + use_unif = 0;
> + else {
> + while (prec-- > 0)
> + pow10 *= 10;
> + /*
> + * If pow10 * (ender - begin) is an integer, use
> + * arc4random_uniform().
> + */
> + use_unif = fmod(pow10 * (ender - begin), 1) == 0;
> + if (use_unif) {
> + uintx = pow10 * (ender - begin);
> +
Re: jot(1) changed behavior
I see two options apart from reverting my commit.
1. Just fix the bug Otto noticed. Remove the section on randomness
completely and fix one example in the manual. That's what the patch
in this mail does. The patch for jot.c is the same as in my previous
mail.
2. Restore the previous behavior when -w or -c is specified together
with -r and fix the bug Otto noticed. I will send this patch in a
second mail.
sobrado@ and I checked that this patch would match the behavior of Linux
and NetBSD. In particular, the format string does not change the output
drastically:
$ jot -r 10 1 3 | sort -n | uniq -c
33148 1
33452 2
33400 3
$ jot -w %d -r 10 1 3 | sort -n | uniq -c
33373 1
33239 2
33388 3
I think this behavior makes sense: if the output consists of integers
anyway, then a %d format should not alter it, independently of what
happens under the hood.
The downside is that it breaks scripts that relied on the previous
behavior that was explicitly mentioned in the manual (as Philippe found
the hard way; sorry about that!).
Index: jot.1
===
RCS file: /var/cvs/src/usr.bin/jot/jot.1,v
retrieving revision 1.19
diff -u -p -r1.19 jot.1
--- jot.1 4 Jan 2016 23:21:28 - 1.19
+++ jot.1 16 Jul 2016 19:09:59 -
@@ -225,41 +225,6 @@ specifying an integer format:
.Bd -literal -offset indent
$ jot -w %d 6 1 10 0.5
.Ed
-.Pp
-For random sequences, the output format also influences the range
-and distribution of the generated numbers:
-.Bd -literal -offset indent
-$ jot -r 10 1 3 | sort -n | uniq -c
-24950 1
-50038 2
-25012 3
-.Ed
-.Pp
-The values at the beginning and end of the interval
-are generated less frequently than the other values.
-There are several ways to solve this problem and generate evenly distributed
-integers:
-.Bd -literal -offset indent
-$ jot -r -p 0 10 0.5 3.5 | sort -n | uniq -c
-33374 1
-33363 2
-33263 3
-
-$ jot -w %d -r 10 1 4 | sort -n | uniq -c
-33306 1
-33473 2
-33221 3
-.Ed
-.Pp
-Note that with random sequences, all numbers generated will
-be smaller than the upper bound.
-The largest value generated will be a tiny bit smaller than
-the upper bound.
-For floating point formats, the value is rounded as described
-before being printed.
-For integer formats, the highest value printed will be one less
-than the requested upper bound, because the generated value will
-be truncated.
.Sh EXAMPLES
Print 21 evenly spaced numbers increasing from \-1 to 1:
.Pp
@@ -280,7 +245,7 @@ comes after the character
.Sq z
in the ASCII character set):
.Pp
-.Dl "$ jot \-r \-c 160 a { | rs \-g0 0 8"
+.Dl "$ jot \-r \-c 160 a z | rs \-g0 0 8"
.Pp
Infinitely many
.Xr yes 1 Ns 's
Index: jot.c
===
RCS file: /var/cvs/src/usr.bin/jot/jot.c,v
retrieving revision 1.27
diff -u -p -r1.27 jot.c
--- jot.c 10 Jan 2016 01:15:52 - 1.27
+++ jot.c 16 Jul 2016 19:10:18 -
@@ -277,9 +277,6 @@ main(int argc, char *argv[])
if (prec > 9) /* pow(10, prec) > UINT32_MAX */
errx(1, "requested precision too large");
- while (prec-- > 0)
- pow10 *= 10;
-
if (ender < begin) {
x = begin;
begin = ender;
@@ -287,16 +284,22 @@ main(int argc, char *argv[])
}
x = ender - begin;
- /*
-* If pow10 * (ender - begin) is an integer, use
-* arc4random_uniform().
-*/
- use_unif = fmod(pow10 * (ender - begin), 1) == 0;
- if (use_unif) {
- uintx = pow10 * (ender - begin);
- if (uintx >= UINT32_MAX)
- errx(1, "requested range too large");
- uintx++;
+ if (prec == 0 && (fmod(ender, 1) != 0 || fmod(begin, 1) != 0))
+ use_unif = 0;
+ else {
+ while (prec-- > 0)
+ pow10 *= 10;
+ /*
+* If pow10 * (ender - begin) is an integer, use
+* arc4random_uniform().
+*/
+ use_unif = fmod(pow10 * (ender - begin), 1) == 0;
+ if (use_unif) {
+ uintx = pow10 * (ender - begin);
+ if (uintx >= UINT32_MAX)
+ errx(1, "requested range too large");
+ uintx++;
+ }
}
for (i = 1; i <= reps || infinity; i++) {
Re: jot(1) changed behavior
This is the second poposal:
In addition to fixing the bug Otto noticed, restore the previous
behavior when -r is used in combination with -w or -c. This is done by
checking whether those flag were specified on the command line.
In particular, we have the following situation:
$ obj/jot -r 10 1 3 | sort -n | uniq -c
33689 1
33171 2
33140 3
$ obj/jot -w %d -r 10 1 3 | sort -n | uniq -c
50043 1
49957 2
The man page bits of this patch are supposed to exhibit this behavior
more clearly.
This matches the behavior of FreeBSD and OS X, but not Linux and NetBSD.
Index: jot.1
===
RCS file: /var/cvs/src/usr.bin/jot/jot.1,v
retrieving revision 1.19
diff -u -p -r1.19 jot.1
--- jot.1 4 Jan 2016 23:21:28 - 1.19
+++ jot.1 16 Jul 2016 19:08:50 -
@@ -227,23 +227,13 @@ $ jot -w %d 6 1 10 0.5
.Ed
.Pp
For random sequences, the output format also influences the range
-and distribution of the generated numbers:
+of the generated numbers:
.Bd -literal -offset indent
-$ jot -r 10 1 3 | sort -n | uniq -c
-24950 1
-50038 2
-25012 3
-.Ed
-.Pp
-The values at the beginning and end of the interval
-are generated less frequently than the other values.
-There are several ways to solve this problem and generate evenly distributed
-integers:
-.Bd -literal -offset indent
-$ jot -r -p 0 10 0.5 3.5 | sort -n | uniq -c
-33374 1
-33363 2
-33263 3
+$ jot -r 10 1 4 | sort -n | uniq -c
+25114 1
+24953 2
+24919 3
+25014 4
$ jot -w %d -r 10 1 4 | sort -n | uniq -c
33306 1
Index: jot.c
===
RCS file: /var/cvs/src/usr.bin/jot/jot.c,v
retrieving revision 1.27
diff -u -p -r1.27 jot.c
--- jot.c 10 Jan 2016 01:15:52 - 1.27
+++ jot.c 16 Jul 2016 19:06:55 -
@@ -85,6 +85,7 @@ main(int argc, char *argv[])
int n = 0;
int ch;
const char*errstr;
+ boolwflag = false;
if (pledge("stdio", NULL) == -1)
err(1, "pledge");
@@ -95,6 +96,7 @@ main(int argc, char *argv[])
randomize = true;
break;
case 'c':
+ wflag = true;
chardata = true;
break;
case 'n':
@@ -107,6 +109,7 @@ main(int argc, char *argv[])
errx(1, "-b word too long");
break;
case 'w':
+ wflag = true;
if (strlcpy(format, optarg, sizeof(format)) >=
sizeof(format))
errx(1, "-w word too long");
@@ -277,9 +280,6 @@ main(int argc, char *argv[])
if (prec > 9) /* pow(10, prec) > UINT32_MAX */
errx(1, "requested precision too large");
- while (prec-- > 0)
- pow10 *= 10;
-
if (ender < begin) {
x = begin;
begin = ender;
@@ -287,16 +287,23 @@ main(int argc, char *argv[])
}
x = ender - begin;
- /*
-* If pow10 * (ender - begin) is an integer, use
-* arc4random_uniform().
-*/
- use_unif = fmod(pow10 * (ender - begin), 1) == 0;
- if (use_unif) {
- uintx = pow10 * (ender - begin);
- if (uintx >= UINT32_MAX)
- errx(1, "requested range too large");
- uintx++;
+ if (wflag ||
+ (prec == 0 && (fmod(ender, 1) != 0 || fmod(begin, 1) != 0)))
+ use_unif = 0;
+ else {
+ while (prec-- > 0)
+ pow10 *= 10;
+ /*
+* If pow10 * (ender - begin) is an integer, use
+* arc4random_uniform().
+*/
+ use_unif = fmod(pow10 * (ender - begin), 1) == 0;
+ if (use_unif) {
+ uintx = pow10 * (ender - begin);
+ if (uintx >= UINT32_MAX)
+ errx(1, "requested range too large");
+ uintx++;
+ }
}
for (i = 1; i <= reps || infinity; i++) {
Re: jot(1) changed behavior
Philippe Meunier wrote: > jot -r 10 1 3 | sort -n | uniq -c > > which the man page clearly indicates should produce something like: > > 24950 1 > 50038 2 > 25012 3 > > which is also more in line with the "generate random floating point > number and truncate to even" model which is described (not very > clearly, IMHO) in the man page. That's an artifact of implementation and the fact that the code was written in a particular way 900 years ago. As a user, 'jot -r 1 1 6' looks like it should give me a fair roll. I should not have to scavenge around in the man page to find out jot uses loaded dice.
Re: jot(1) changed behavior
Theo Buehler wrote: >$ jot -r -p 0 10 1 3 | sort -n | uniq -c >33464 1 >33246 2 >33290 3 According to the man page, "in the absence of -p, the precision is the greater of the numbers begin and end". Since both 1 and 3 have a precision of zero, therefore I would expect your command: jot -r -p 0 10 1 3 | sort -n | uniq -c to behave exactly the same way as this one: jot -r 10 1 3 | sort -n | uniq -c which the man page clearly indicates should produce something like: 24950 1 50038 2 25012 3 which is also more in line with the "generate random floating point number and truncate to even" model which is described (not very clearly, IMHO) in the man page. Philippe
Re: jot(1) changed behavior
> The second exmaple:
>
> $ jot -r -p 0 10 0.5 3.5 | sort -n | uniq -c
> 25120 0
> 49882 2
> 24998 4
>
> So I'd says there are real bugs introduced with the latest commit.
>
> -Otto
>
Indeed, this is bad. The following patch lets the code fall back to the
old version in the cases that the new code doesn't handle well:
As we discussed on icb, if -p 0 is given, only use the new code if both
endpoints are integers seems to work nicely.
$ jot -r -p 0 10 0.5 3.5 | sort -n | uniq -c
33434 1
33228 2
8 3
$ jot -r -p 0 10 1 3 | sort -n | uniq -c
33464 1
33246 2
33290 3
Bad bias in some cases is unavoidable:
$ jot -r -p 0 10 1 3.5 | sort -n | uniq -c
19923 1
39934 2
40143 3
Index: jot.c
===
RCS file: /var/cvs/src/usr.bin/jot/jot.c,v
retrieving revision 1.27
diff -u -p -r1.27 jot.c
--- jot.c 10 Jan 2016 01:15:52 - 1.27
+++ jot.c 15 Jul 2016 06:26:29 -
@@ -277,9 +277,6 @@ main(int argc, char *argv[])
if (prec > 9) /* pow(10, prec) > UINT32_MAX */
errx(1, "requested precision too large");
- while (prec-- > 0)
- pow10 *= 10;
-
if (ender < begin) {
x = begin;
begin = ender;
@@ -287,16 +284,22 @@ main(int argc, char *argv[])
}
x = ender - begin;
- /*
-* If pow10 * (ender - begin) is an integer, use
-* arc4random_uniform().
-*/
- use_unif = fmod(pow10 * (ender - begin), 1) == 0;
- if (use_unif) {
- uintx = pow10 * (ender - begin);
- if (uintx >= UINT32_MAX)
- errx(1, "requested range too large");
- uintx++;
+ if (prec == 0 && (fmod(ender, 1) != 0 || fmod(begin, 1) != 0))
+ use_unif = 0;
+ else {
+ while (prec-- > 0)
+ pow10 *= 10;
+ /*
+* If pow10 * (ender - begin) is an integer, use
+* arc4random_uniform().
+*/
+ use_unif = fmod(pow10 * (ender - begin), 1) == 0;
+ if (use_unif) {
+ uintx = pow10 * (ender - begin);
+ if (uintx >= UINT32_MAX)
+ errx(1, "requested range too large");
+ uintx++;
+ }
}
for (i = 1; i <= reps || infinity; i++) {
Re: jot(1) changed behavior
On Thu, Jul 14, 2016 at 08:42:55PM -0400, Ted Unangst wrote: > Philippe Meunier wrote: > > Looking at the cvs log for jot.c, this seems to be a known change: > > > > "revision 1.27 [...] Internally, jot -r now uses arc4random_uniform() > > whenever this is clearly possible. In particular `jot -r 1 10 20' > > yields an unbiased random number between 10 and 20 (both ends > > inclusive) from the shell." > > > > I only discovered this change today after noticing that one of my > > shell scripts that used to work fine had started to fail with a low > > probability: the script uses jot(1) to generate a sequence of random > > array indexes, and with this change an index can now be out of bounds > > with a probability of about 1/1700. Fortunately it isn't an important > > script but given the low probability of failure it wasn't exactly fun > > to debug. Anyway, I don't know which one of jot or jot's man page is > > going to be fixed but I'd advocate for reverting to the previous > > behavior to preserve the semantics of scripts that rely on it. > > The current behavior seems far better (though I realize it's different.) I > have difficulty understanding what the man page is trying to say. Something > about expect the unexpected I think. I'd much rather delete all that nonsense. IMO, the changes have been done without much care, breaking what's documented. There are thee examples using -r in the man pages. 2 of them are now broken. The second exmaple: $ jot -r -p 0 10 0.5 3.5 | sort -n | uniq -c 25120 0 49882 2 24998 4 So I'd says there are real bugs introduced with the latest commit. -Otto
Re: jot(1) changed behavior
Philippe Meunier wrote: > Looking at the cvs log for jot.c, this seems to be a known change: > > "revision 1.27 [...] Internally, jot -r now uses arc4random_uniform() > whenever this is clearly possible. In particular `jot -r 1 10 20' > yields an unbiased random number between 10 and 20 (both ends > inclusive) from the shell." > > I only discovered this change today after noticing that one of my > shell scripts that used to work fine had started to fail with a low > probability: the script uses jot(1) to generate a sequence of random > array indexes, and with this change an index can now be out of bounds > with a probability of about 1/1700. Fortunately it isn't an important > script but given the low probability of failure it wasn't exactly fun > to debug. Anyway, I don't know which one of jot or jot's man page is > going to be fixed but I'd advocate for reverting to the previous > behavior to preserve the semantics of scripts that rely on it. The current behavior seems far better (though I realize it's different.) I have difficulty understanding what the man page is trying to say. Something about expect the unexpected I think. I'd much rather delete all that nonsense.
Re: jot(1) changed behavior
On 16-07-14 17:55:00, Edgar Pettijohn wrote:
> On 16-07-14 12:00:21, Philippe Meunier wrote:
> > Hello,
> >
> > According to jot(1)'s man page:
> >
> > "$ jot -w %d -r 10 1 4 | sort -n | uniq -c
> > 33306 1
> > 33473 2
> > 33221 3
> >
> > Note that with random sequences, all numbers generated will be smaller
> > than the upper bound. The largest value generated will be a tiny bit
> > smaller than the upper bound. For floating point formats, the value
> > is rounded as described before being printed. For integer formats,
> > the highest value printed will be one less than the requested upper
> > bound, because the generated value will be truncated."
> >
> > The "smaller than the upper bound" part used to be correct but not
> > anymore:
> >
> > $ uname -a
> > OpenBSD something.somewhere 5.9 GENERIC#1561 i386
> > $ jot -w %d -r 10 1 4 | sort -n | uniq -c
> > 24729 1
> > 25035 2
> > 25106 3
> > 25130 4
> >
> > Looking at the cvs log for jot.c, this seems to be a known change:
> >
> > "revision 1.27 [...] Internally, jot -r now uses arc4random_uniform()
> > whenever this is clearly possible. In particular `jot -r 1 10 20'
> > yields an unbiased random number between 10 and 20 (both ends
> > inclusive) from the shell."
> >
> > I only discovered this change today after noticing that one of my
> > shell scripts that used to work fine had started to fail with a low
> > probability: the script uses jot(1) to generate a sequence of random
> > array indexes, and with this change an index can now be out of bounds
> > with a probability of about 1/1700. Fortunately it isn't an important
> > script but given the low probability of failure it wasn't exactly fun
> > to debug. Anyway, I don't know which one of jot or jot's man page is
> > going to be fixed but I'd advocate for reverting to the previous
> > behavior to preserve the semantics of scripts that rely on it.
> >
> > Cheers,
> >
> > Philippe
> >
> Try this patch. I don't use jot, but in my simple testing I think this is
> what you are looking for.
> --
> Edgar Pettijohn
> Index: jot.c
> ===
> RCS file: /cvs/src/usr.bin/jot/jot.c,v
> retrieving revision 1.27
> diff -u -p -u -r1.27 jot.c
> --- jot.c 10 Jan 2016 01:15:52 - 1.27
> +++ jot.c 14 Jul 2016 22:53:41 -
> @@ -296,7 +296,6 @@ main(int argc, char *argv[])
> uintx = pow10 * (ender - begin);
> if (uintx >= UINT32_MAX)
> errx(1, "requested range too large");
> - uintx++;
> }
>
> for (i = 1; i <= reps || infinity; i++) {
>
This ends up breaking other use cases.
--
Edgar Pettijohn
Re: jot(1) changed behavior
On 16-07-14 12:00:21, Philippe Meunier wrote:
> Hello,
>
> According to jot(1)'s man page:
>
> "$ jot -w %d -r 10 1 4 | sort -n | uniq -c
> 33306 1
> 33473 2
> 33221 3
>
> Note that with random sequences, all numbers generated will be smaller
> than the upper bound. The largest value generated will be a tiny bit
> smaller than the upper bound. For floating point formats, the value
> is rounded as described before being printed. For integer formats,
> the highest value printed will be one less than the requested upper
> bound, because the generated value will be truncated."
>
> The "smaller than the upper bound" part used to be correct but not
> anymore:
>
> $ uname -a
> OpenBSD something.somewhere 5.9 GENERIC#1561 i386
> $ jot -w %d -r 10 1 4 | sort -n | uniq -c
> 24729 1
> 25035 2
> 25106 3
> 25130 4
>
> Looking at the cvs log for jot.c, this seems to be a known change:
>
> "revision 1.27 [...] Internally, jot -r now uses arc4random_uniform()
> whenever this is clearly possible. In particular `jot -r 1 10 20'
> yields an unbiased random number between 10 and 20 (both ends
> inclusive) from the shell."
>
> I only discovered this change today after noticing that one of my
> shell scripts that used to work fine had started to fail with a low
> probability: the script uses jot(1) to generate a sequence of random
> array indexes, and with this change an index can now be out of bounds
> with a probability of about 1/1700. Fortunately it isn't an important
> script but given the low probability of failure it wasn't exactly fun
> to debug. Anyway, I don't know which one of jot or jot's man page is
> going to be fixed but I'd advocate for reverting to the previous
> behavior to preserve the semantics of scripts that rely on it.
>
> Cheers,
>
> Philippe
>
Try this patch. I don't use jot, but in my simple testing I think this is
what you are looking for.
--
Edgar Pettijohn
Index: jot.c
===
RCS file: /cvs/src/usr.bin/jot/jot.c,v
retrieving revision 1.27
diff -u -p -u -r1.27 jot.c
--- jot.c 10 Jan 2016 01:15:52 - 1.27
+++ jot.c 14 Jul 2016 22:53:41 -
@@ -296,7 +296,6 @@ main(int argc, char *argv[])
uintx = pow10 * (ender - begin);
if (uintx >= UINT32_MAX)
errx(1, "requested range too large");
- uintx++;
}
for (i = 1; i <= reps || infinity; i++) {
