------=_Part_4766_939722632.1423084970882
Content-Type: multipart/alternative;
 boundary="----=_Part_4767_1323535986.1423084970882"

------=_Part_4767_1323535986.1423084970882
Content-Type: text/plain; charset=UTF-8

I think that it would be useful to have an arithmetic/number-theoretic
modulo library function, say std::arith_div and std::arith_mod.  The
difference would be that a negative dividend would still result in a
positive remainder: (-1) % 5 == 4.

This would be useful for number-theoretic purposes, particularly if a
big-number library is eventually added.

Melissa

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

------=_Part_4767_1323535986.1423084970882
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">I think that it would be useful to have an arithmetic/numb=
er-theoretic modulo library function, say std::arith_div and std::arith_mod=
..&nbsp; The difference would be that a negative dividend would still result=
 in a positive remainder: (-1) % 5 =3D=3D 4.<br><br>This would be useful fo=
r number-theoretic purposes, particularly if a big-number library is eventu=
ally added.<br><br>Melissa<br></div>

<p></p>

-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

------=_Part_4767_1323535986.1423084970882--
------=_Part_4766_939722632.1423084970882--

.

On 2015-02-04 16:22, Myriachan wrote:
> I think that it would be useful to have an arithmetic/number-theoretic
> modulo library function, say std::arith_div and std::arith_mod.  The
> difference would be that a negative dividend would still result in a
> positive remainder: (-1) % 5 == 4.
>
> This would be useful for number-theoretic purposes, particularly if a
> big-number library is eventually added.

Yes, please!  The best way to achieve this by hand is not obvious, so
it's a good candidate for the std library.

(I would also like std::divide_round_up)

John Bytheway

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

.

--Apple-Mail=_B5D9729A-E2BC-4558-9604-2C2E098D6471
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset=UTF-8


> On 2015=E2=80=9302=E2=80=9305, at 5:22 AM, Myriachan <myriachan@gmail.com=
> wrote:
>=20
> I think that it would be useful to have an arithmetic/number-theoretic mo=
dulo library function, say std::arith_div and std::arith_mod.  The differen=
ce would be that a negative dividend would still result in a positive remai=
nder: (-1) % 5 =3D=3D 4.

Or e.g. std::ring_mod or std::residue. I=E2=80=99m bikeshedding, but everyt=
hing is arithmetic in some way or another; the name should be reminiscent o=
f introductory number theory.

> This would be useful for number-theoretic purposes, particularly if a big=
-number library is eventually added.

+1. I got bit by this several times before I learned my lesson. (Although m=
y bad experiences were back in the day when some implementations actually p=
rovided this behavior with the built-in operator.)

As for the =E2=80=9Cbest way to achieve this by hand,=E2=80=9D at least for=
 a constant modulus and with my brainpower: Convert the signed number to un=
signed, add the MSB, subtract the residue of the MSB=E2=80=99s value, then =
divide and multiply that by the modulus, and subtract. The answer will be w=
rong if the =E2=80=9Csubtract MSB residue=E2=80=9D wraps around, so you hav=
e to require for residue(arg, modulus) that (arg - modulus) be representabl=
e.

The compiler can do better, and sidestep that requirement, though. It only =
needs to do a low-order, sign-agnostic multiplication as if it=E2=80=99s go=
ing to divide by the (constant) modulus, but take the fractional bits. Unsi=
gned-multiply that result by the modulus and take the high-order bits. Voil=
a, the residual.

TL;DR: most folks will not come up with an efficient formula on their own, =
and the compiler with particular numbers and instructions on-hand has a dis=
tinct advantage over even clever users.

--=20

---=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/.

--Apple-Mail=_B5D9729A-E2BC-4558-9604-2C2E098D6471
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html; charset=UTF-8

<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html charset=
=3Dutf-8"></head><body style=3D"word-wrap: break-word; -webkit-nbsp-mode: s=
pace; -webkit-line-break: after-white-space;" class=3D""><br class=3D""><di=
v><blockquote type=3D"cite" class=3D""><div class=3D"">On 2015=E2=80=9302=
=E2=80=9305, at 5:22 AM, Myriachan &lt;<a href=3D"mailto:myriachan@gmail.co=
m" class=3D"">myriachan@gmail.com</a>&gt; wrote:</div><br class=3D"Apple-in=
terchange-newline"><div class=3D""><div dir=3D"ltr" class=3D"">I think that=
 it would be useful to have an arithmetic/number-theoretic modulo library f=
unction, say std::arith_div and std::arith_mod.&nbsp; The difference would =
be that a negative dividend would still result in a positive remainder: (-1=
) % 5 =3D=3D 4.<br class=3D""></div></div></blockquote><div><br class=3D"">=
</div><div>Or e.g. <font face=3D"Courier" class=3D"">std::ring_mod</font>&n=
bsp;or <font face=3D"Courier" class=3D"">std::residue</font>. I=E2=80=99m b=
ikeshedding, but everything is arithmetic in some way or another; the name =
should be reminiscent of introductory number theory.</div><br class=3D""><b=
lockquote type=3D"cite" class=3D""><div class=3D""><div dir=3D"ltr" class=
=3D"">This would be useful for number-theoretic purposes, particularly if a=
 big-number library is eventually added.<br class=3D""></div></div></blockq=
uote><div><br class=3D""></div><div>+1. I got bit by this several times bef=
ore I learned my lesson. (Although my bad experiences were back in the day =
when some implementations actually provided this behavior with the built-in=
 operator.)</div><div><br class=3D""></div><div>As for the =E2=80=9Cbest wa=
y to achieve this by hand,=E2=80=9D at least for a constant modulus and wit=
h my brainpower: Convert the signed number to unsigned, add the MSB, subtra=
ct the residue of the MSB=E2=80=99s value, then divide and multiply that by=
 the modulus, and subtract. The answer will be wrong if the =E2=80=9Csubtra=
ct MSB residue=E2=80=9D wraps around, so you have to require for <font face=
=3D"Courier" class=3D"">residue(arg, modulus)</font> that <font face=3D"Cou=
rier" class=3D"">(arg - modulus)</font> be representable.</div><div><br cla=
ss=3D""></div><div>The compiler can do better, and sidestep that requiremen=
t, though. It only needs to do a low-order, sign-agnostic multiplication as=
 if it=E2=80=99s going to divide by the (constant) modulus, but take the fr=
actional bits. Unsigned-multiply that result by the modulus and take the hi=
gh-order bits. Voila, the residual.</div><div><br class=3D""></div><div>TL;=
DR: most folks will not come up with an efficient formula on their own, and=
 the compiler with particular numbers and instructions on-hand has a distin=
ct advantage over even clever users.</div></div></body></html>

<p></p>

-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

--Apple-Mail=_B5D9729A-E2BC-4558-9604-2C2E098D6471--

.

What about a pow_mod?

On 2/8/15, David Krauss <potswa@gmail.com> wrote:
>
>> On 2015=E2=80=9302=E2=80=9305, at 5:22 AM, Myriachan <myriachan@gmail.co=
m> wrote:
>>
>> I think that it would be useful to have an arithmetic/number-theoretic
>> modulo library function, say std::arith_div and std::arith_mod.  The
>> difference would be that a negative dividend would still result in a
>> positive remainder: (-1) % 5 =3D=3D 4.
>
> Or e.g. std::ring_mod or std::residue. I=E2=80=99m bikeshedding, but ever=
ything is
> arithmetic in some way or another; the name should be reminiscent of
> introductory number theory.
>
>> This would be useful for number-theoretic purposes, particularly if a
>> big-number library is eventually added.
>
> +1. I got bit by this several times before I learned my lesson. (Although=
 my
> bad experiences were back in the day when some implementations actually
> provided this behavior with the built-in operator.)
>
> As for the =E2=80=9Cbest way to achieve this by hand,=E2=80=9D at least f=
or a constant
> modulus and with my brainpower: Convert the signed number to unsigned, ad=
d
> the MSB, subtract the residue of the MSB=E2=80=99s value, then divide and=
 multiply
> that by the modulus, and subtract. The answer will be wrong if the =E2=80=
=9Csubtract
> MSB residue=E2=80=9D wraps around, so you have to require for residue(arg=
, modulus)
> that (arg - modulus) be representable.
>
> The compiler can do better, and sidestep that requirement, though. It onl=
y
> needs to do a low-order, sign-agnostic multiplication as if it=E2=80=99s =
going to
> divide by the (constant) modulus, but take the fractional bits.
> Unsigned-multiply that result by the modulus and take the high-order bits=
..
> Voila, the residual.
>
> TL;DR: most folks will not come up with an efficient formula on their own=
,
> and the compiler with particular numbers and instructions on-hand has a
> distinct advantage over even clever users.
>
> --
>
> ---
> You received this message because you are subscribed to the Google Groups
> "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to std-proposals+unsubscribe@isocpp.org.
> To post to this group, send email to std-proposals@isocpp.org.
> Visit this group at
> http://groups.google.com/a/isocpp.org/group/std-proposals/.
>

--=20

---=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/.

.

> On 2015=E2=80=9302=E2=80=9308, at 3:38 PM, Douglas Boffey <douglas.boffey=
@gmail.com> wrote:
>=20
> What about a pow_mod?

Perhaps it fits, but when is that function used with a signed argument?

(a^b mod c) is used in cryptography, but the simpler (a mod b) with signed =
a comes up when treating array elements in some cyclic fashion, and you hav=
e a negative indexing offset.

--=20

---=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/.

.

------=_Part_2570_1148064901.1423510292763
Content-Type: multipart/alternative;
 boundary="----=_Part_2571_386222812.1423510292763"

------=_Part_2571_386222812.1423510292763
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable


On Saturday, February 7, 2015 at 11:18:35 PM UTC-8, David Krauss wrote:

> Or e.g. std::ring_mod or std::residue. I=E2=80=99m bikeshedding, but ever=
ything=20
> is arithmetic in some way or another; the name should be reminiscent of=
=20
> introductory number theory.
>
>
I like std::ring_mod and std::residue, certainly more than std::arith_mod. =
=20
But which of those two is better? =3D^-^=3D


On Saturday, February 7, 2015 at 11:38:08 PM UTC-8, Douglas Boffey wrote:

> What about a pow_mod?=20
>

>
The reason I mentioned this idea is that this function ought to be defined=
=20
so that a big-number library will fit right in and support the same=20
operations.  Maybe a big-number library proposal could define these=20
functions for the built-in types as well?


On Sunday, February 8, 2015 at 12:21:04 AM UTC-8, David Krauss wrote:
>
> Perhaps it fits, but when is that function used with a signed argument?=
=20
>
>
I use pow_mod functions with potentially-negative arguments all the time=20
when working with public-key cryptography, but it's just implicitly doing a=
=20
ring_mod / residue first.  In the typical literature surrounding number=20
theory and cryptography, it's often not stated that this happens.  To use=
=20
an example from SRP-6a, expressions like "(*B* - *kg*^*x*)^(*a* + *ux*)=20
(mod *N*)" may have "*B* - *kg*^*x*" less than zero, and it's just implicit=
=20
that the final result passed over the wire will be the positive form.  (^=
=20
is power not XOR in this example.)


Melissa

--=20

---=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/.

------=_Part_2571_386222812.1423510292763
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div></div><div>On Saturday, February 7, 2015 at 11:18:35 =
PM UTC-8, David Krauss wrote:<br></div><blockquote class=3D"gmail_quote" st=
yle=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-lef=
t: 1ex;"><div style=3D"word-wrap:break-word"><div><div>Or e.g. <font face=
=3D"Courier">std::ring_mod</font>&nbsp;or <font face=3D"Courier">std::resid=
ue</font>.
 I=E2=80=99m bikeshedding, but everything is arithmetic in some way or anot=
her;=20
the name should be reminiscent of introductory number theory.</div><br></di=
v></div></blockquote><div><br>I like <span style=3D"font-family: courier ne=
w,monospace;">std::ring_mod</span> and <span style=3D"font-family: courier =
new,monospace;">std::residue</span>, certainly more than <span style=3D"fon=
t-family: courier new,monospace;">std::arith_mod</span>.&nbsp; But which of=
 those two is better? =3D^-^=3D<br><br><br>On Saturday, February 7, 2015 at=
 11:38:08 PM UTC-8, Douglas Boffey wrote:<br><blockquote style=3D"margin: 0=
px 0px 0px 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: =
1ex;" class=3D"gmail_quote">What about a pow_mod?
<br></blockquote><blockquote style=3D"margin: 0px 0px 0px 0.8ex; border-lef=
t: 1px solid rgb(204, 204, 204); padding-left: 1ex;" class=3D"gmail_quote">
<br></blockquote><br>The reason I mentioned this idea is that this function=
 ought to be defined so that a big-number library will fit right in and sup=
port the same operations.&nbsp; Maybe a big-number library proposal could d=
efine these functions for the built-in types as well?<br></div><br><br>On S=
unday, February 8, 2015 at 12:21:04 AM UTC-8, David Krauss wrote:<blockquot=
e class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: =
1px #ccc solid;padding-left: 1ex;">
Perhaps it fits, but when is that function used with a signed argument?
<br>
<br></blockquote><div><br>I use <span style=3D"font-family: courier new,mon=
ospace;">pow_mod</span> functions with potentially-negative arguments all t=
he time when working with public-key cryptography, but it's just implicitly=
 doing a <span style=3D"font-family: courier new,monospace;">ring_mod</span=
> / <span style=3D"font-family: courier new,monospace;">residue</span> firs=
t.&nbsp; In the typical literature surrounding number theory and cryptograp=
hy, it's often not stated that this happens.&nbsp; To use an example from S=
RP-6a, expressions like "(<i>B</i> - <i>kg</i>^<i>x</i>)^(<i>a</i> + <i>ux<=
/i>) (mod <i>N</i>)" may have "<i>B</i> - <i>kg</i>^<i>x</i>" less than zer=
o, and it's just implicit that the final result passed over the wire will b=
e the positive form.&nbsp; (^ is power not XOR in this example.)</div><br><=
br>Melissa<br></div>

<p></p>

-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

------=_Part_2571_386222812.1423510292763--
------=_Part_2570_1148064901.1423510292763--

.