Integer bit size and the modulus operator

classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

Integer bit size and the modulus operator

Ionut Florescu
I am a statistician and I come up to an interesting problem in
cryptography. I would like to use R since there are some statistical
procedures that I need to use.
However, I run into a problem when using the modulus operator %%.

I am using R 2.2.1 and when I calculate modulus for large numbers (that
I need with my problem) R gives me warnings. For instance if one does:
a=1:40;
8^a %% 41
one obtains zeros which is not possible since 8 to any power is not a
multiple of 41.
In addition when working with numbers larger that this and with the mod
operator R crashes randomly.

I believe this is because R stores large integers as real numbers thus
there may be lack of accuracy when applying the modulus operator and
converting back to integers.

So my question is this: Is it possible to increase the size of memory
used for storing integers? Say from 32 bits to 512 bits (Typical size of
integers in cryptography).

Thank you, any help would be greatly appreciated.
Ionut Florescu

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: Integer bit size and the modulus operator

jholtman
You have reached the maximum value that can be stored accurately in a
floating point number.  That is what the error message is telling you.  I
get 21 warnings and this says that at 8^20 I am now truncating digits in the
variable.  You only have about 54 bits in the floating point number and you
exceed this about 8^19.

> a=1:40;
> 8^a %% 41
 [1]  8 23 20 37  9 31  2 16  5 40 33 18 21  4 32 10 39 25 36  1  8 23 20
37  9 31  2 16  5 40 33
[32] 18 21  4 32 10  0  0  0  0
There were 21 warnings (use warnings() to see them)
> warnings()
Warning messages:
1: probable complete loss of accuracy in modulus
2: probable complete loss of accuracy in modulus
3: probable complete loss of accuracy in modulus
4: probable complete loss of accuracy in modulus
5: probable complete loss of accuracy in modulus
6: probable complete loss of accuracy in modulus
7: probable complete loss of accuracy in modulus
8: probable complete loss of accuracy in modulus
9: probable complete loss of accuracy in modulus
10: probable complete loss of accuracy in modulus
11: probable complete loss of accuracy in modulus
12: probable complete loss of accuracy in modulus
13: probable complete loss of accuracy in modulus
14: probable complete loss of accuracy in modulus
15: probable complete loss of accuracy in modulus
16: probable complete loss of accuracy in modulus
17: probable complete loss of accuracy in modulus
18: probable complete loss of accuracy in modulus
19: probable complete loss of accuracy in modulus
20: probable complete loss of accuracy in modulus
21: probable complete loss of accuracy in modulus
>
> 8^35
[1] 4.056482e+31
> 8^36
[1] 3.245186e+32
> 8^19
[1] 1.441152e+17
> 8^19%%41
[1] 36
> 8^20
[1] 1.152922e+18
> 8^20%%41
[1] 1
Warning message:
probable complete loss of accuracy in modulus
>



On 1/30/06, Ionut Florescu <[hidden email]> wrote:

>
> I am a statistician and I come up to an interesting problem in
> cryptography. I would like to use R since there are some statistical
> procedures that I need to use.
> However, I run into a problem when using the modulus operator %%.
>
> I am using R 2.2.1 and when I calculate modulus for large numbers (that
> I need with my problem) R gives me warnings. For instance if one does:
> a=1:40;
> 8^a %% 41
> one obtains zeros which is not possible since 8 to any power is not a
> multiple of 41.
> In addition when working with numbers larger that this and with the mod
> operator R crashes randomly.
>
> I believe this is because R stores large integers as real numbers thus
> there may be lack of accuracy when applying the modulus operator and
> converting back to integers.
>
> So my question is this: Is it possible to increase the size of memory
> used for storing integers? Say from 32 bits to 512 bits (Typical size of
> integers in cryptography).
>
> Thank you, any help would be greatly appreciated.
> Ionut Florescu
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide!
> http://www.R-project.org/posting-guide.html
>



--
Jim Holtman
Cincinnati, OH
+1 513 247 0281

What the problem you are trying to solve?

        [[alternative HTML version deleted]]

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: Integer bit size and the modulus operator

Duncan Murdoch
In reply to this post by Ionut Florescu
On 1/30/2006 11:32 AM, Ionut Florescu wrote:

> I am a statistician and I come up to an interesting problem in
> cryptography. I would like to use R since there are some statistical
> procedures that I need to use.
> However, I run into a problem when using the modulus operator %%.
>
> I am using R 2.2.1 and when I calculate modulus for large numbers (that
> I need with my problem) R gives me warnings. For instance if one does:
> a=1:40;
> 8^a %% 41
> one obtains zeros which is not possible since 8 to any power is not a
> multiple of 41.
> In addition when working with numbers larger that this and with the mod
> operator R crashes randomly.

Could you keep a record of the random crashes, and see if you can make
any of them repeatable?  R shouldn't crash.  If you can find a
repeatable way to make it crash, then that's a bug that needs to be
fixed.  (If it crashes at random it should still be fixed, but it's so
much harder to fix that it's unlikely to happen unless the cases are
ones that look likely to come up in normal situations.)


>
> I believe this is because R stores large integers as real numbers thus
> there may be lack of accuracy when applying the modulus operator and
> converting back to integers.
>
> So my question is this: Is it possible to increase the size of memory
> used for storing integers? Say from 32 bits to 512 bits (Typical size of
> integers in cryptography).

No, but there is at least one contributed package that does multiple
precision integer arithmetic.  I can't remember the name of it right
now, but Google should be able to find it for you...

Duncan Murdoch
>
> Thank you, any help would be greatly appreciated.
> Ionut Florescu
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: Integer bit size and the modulus operator

Liaw, Andy
In reply to this post by Ionut Florescu
R is probably not the best tool for handling large integers...

AFAIK Python has the interesting feature of not only having a `long' integer
type (that can store arbitrarily large integers), but can convert a regular
4-byte int to the `long' type when necessary.  Perhaps that would be a
better tool for the purpose.

Andy

From: jim holtman

>
> You have reached the maximum value that can be stored accurately in a
> floating point number.  That is what the error message is
> telling you.  I
> get 21 warnings and this says that at 8^20 I am now
> truncating digits in the
> variable.  You only have about 54 bits in the floating point
> number and you
> exceed this about 8^19.
>
> > a=1:40;
> > 8^a %% 41
>  [1]  8 23 20 37  9 31  2 16  5 40 33 18 21  4 32 10 39 25 36
>  1  8 23 20
> 37  9 31  2 16  5 40 33
> [32] 18 21  4 32 10  0  0  0  0
> There were 21 warnings (use warnings() to see them)
> > warnings()
> Warning messages:
> 1: probable complete loss of accuracy in modulus
> 2: probable complete loss of accuracy in modulus
> 3: probable complete loss of accuracy in modulus
> 4: probable complete loss of accuracy in modulus
> 5: probable complete loss of accuracy in modulus
> 6: probable complete loss of accuracy in modulus
> 7: probable complete loss of accuracy in modulus
> 8: probable complete loss of accuracy in modulus
> 9: probable complete loss of accuracy in modulus
> 10: probable complete loss of accuracy in modulus
> 11: probable complete loss of accuracy in modulus
> 12: probable complete loss of accuracy in modulus
> 13: probable complete loss of accuracy in modulus
> 14: probable complete loss of accuracy in modulus
> 15: probable complete loss of accuracy in modulus
> 16: probable complete loss of accuracy in modulus
> 17: probable complete loss of accuracy in modulus
> 18: probable complete loss of accuracy in modulus
> 19: probable complete loss of accuracy in modulus
> 20: probable complete loss of accuracy in modulus
> 21: probable complete loss of accuracy in modulus
> >
> > 8^35
> [1] 4.056482e+31
> > 8^36
> [1] 3.245186e+32
> > 8^19
> [1] 1.441152e+17
> > 8^19%%41
> [1] 36
> > 8^20
> [1] 1.152922e+18
> > 8^20%%41
> [1] 1
> Warning message:
> probable complete loss of accuracy in modulus
> >
>
>
>
> On 1/30/06, Ionut Florescu <[hidden email]> wrote:
> >
> > I am a statistician and I come up to an interesting problem in
> > cryptography. I would like to use R since there are some statistical
> > procedures that I need to use.
> > However, I run into a problem when using the modulus operator %%.
> >
> > I am using R 2.2.1 and when I calculate modulus for large
> numbers (that
> > I need with my problem) R gives me warnings. For instance
> if one does:
> > a=1:40;
> > 8^a %% 41
> > one obtains zeros which is not possible since 8 to any
> power is not a
> > multiple of 41.
> > In addition when working with numbers larger that this and
> with the mod
> > operator R crashes randomly.
> >
> > I believe this is because R stores large integers as real
> numbers thus
> > there may be lack of accuracy when applying the modulus operator and
> > converting back to integers.
> >
> > So my question is this: Is it possible to increase the size
> of memory
> > used for storing integers? Say from 32 bits to 512 bits
> (Typical size of
> > integers in cryptography).
> >
> > Thank you, any help would be greatly appreciated.
> > Ionut Florescu
> >
> > ______________________________________________
> > [hidden email] mailing list
> > https://stat.ethz.ch/mailman/listinfo/r-help
> > PLEASE do read the posting guide!
> > http://www.R-project.org/posting-guide.html
> >
>
>
>
> --
> Jim Holtman
> Cincinnati, OH
> +1 513 247 0281
>
> What the problem you are trying to solve?
>
> [[alternative HTML version deleted]]
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide!
> http://www.R-project.org/posting-guide.html
>
>

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: Integer bit size and the modulus operator

Ionut Florescu
In reply to this post by Duncan Murdoch
Thank you for the quick reply, I will look into the R packages.
For crashing R try this:

generator.zp=function(x,p)
{a=1:(p-1); b=x^a%%p;
if(all(b[1:(p-2)]!=1)&&(b[p-1]==1)){return(x, " Good ")}
else{return(x, " No Good, try another integer ")}
}

This checks if element x is a generator of the group Z_p. If you try
this function for p = 41 and x various increasing values eventually it
will crash R. That is what I meant by random, at first I started x=2,3
so on, when I got to 8, R crashed. Now apparently I can get to 15. When
I tried again I got to 20.

Ionut Florescu


Duncan Murdoch wrote:

> On 1/30/2006 11:32 AM, Ionut Florescu wrote:
>> I am a statistician and I come up to an interesting problem in
>> cryptography. I would like to use R since there are some statistical
>> procedures that I need to use.
>> However, I run into a problem when using the modulus operator %%.
>>
>> I am using R 2.2.1 and when I calculate modulus for large numbers
>> (that I need with my problem) R gives me warnings. For instance if
>> one does:
>> a=1:40;
>> 8^a %% 41
>> one obtains zeros which is not possible since 8 to any power is not a
>> multiple of 41.
>> In addition when working with numbers larger that this and with the
>> mod operator R crashes randomly.
>
> Could you keep a record of the random crashes, and see if you can make
> any of them repeatable?  R shouldn't crash.  If you can find a
> repeatable way to make it crash, then that's a bug that needs to be
> fixed.  (If it crashes at random it should still be fixed, but it's so
> much harder to fix that it's unlikely to happen unless the cases are
> ones that look likely to come up in normal situations.)
>
>
>>
>> I believe this is because R stores large integers as real numbers
>> thus there may be lack of accuracy when applying the modulus operator
>> and converting back to integers.
>>
>> So my question is this: Is it possible to increase the size of memory
>> used for storing integers? Say from 32 bits to 512 bits (Typical size
>> of integers in cryptography).
>
> No, but there is at least one contributed package that does multiple
> precision integer arithmetic.  I can't remember the name of it right
> now, but Google should be able to find it for you...
>
> Duncan Murdoch
>>
>> Thank you, any help would be greatly appreciated.
>> Ionut Florescu
>>
>> ______________________________________________
>> [hidden email] mailing list
>> https://stat.ethz.ch/mailman/listinfo/r-help
>> PLEASE do read the posting guide!
>> http://www.R-project.org/posting-guide.html
>
>

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: Integer bit size and the modulus operator

Duncan Murdoch
On 1/30/2006 1:39 PM, Ionut Florescu wrote:
> Thank you for the quick reply, I will look into the R packages.
> For crashing R try this:
>
> generator.zp=function(x,p)
> {a=1:(p-1); b=x^a%%p;
> if(all(b[1:(p-2)]!=1)&&(b[p-1]==1)){return(x, " Good ")}
> else{return(x, " No Good, try another integer ")}
> }

Thanks, I can reproduce the crash using

for (x in 10:100) generator.zp(x, 41)

I'll see if I can track down what's going wrong.  By the way, you're not
supposed to use two arguments to return():  that's not supposed to be
allowed any more.  I'm somewhat surprised you don't get an error from
it.  But that's not the cause of the crash.

Duncan Murdoch


>
> This checks if element x is a generator of the group Z_p. If you try
> this function for p = 41 and x various increasing values eventually it
> will crash R. That is what I meant by random, at first I started x=2,3
> so on, when I got to 8, R crashed. Now apparently I can get to 15. When
> I tried again I got to 20.
>
> Ionut Florescu
>
>
> Duncan Murdoch wrote:
>> On 1/30/2006 11:32 AM, Ionut Florescu wrote:
>>> I am a statistician and I come up to an interesting problem in
>>> cryptography. I would like to use R since there are some statistical
>>> procedures that I need to use.
>>> However, I run into a problem when using the modulus operator %%.
>>>
>>> I am using R 2.2.1 and when I calculate modulus for large numbers
>>> (that I need with my problem) R gives me warnings. For instance if
>>> one does:
>>> a=1:40;
>>> 8^a %% 41
>>> one obtains zeros which is not possible since 8 to any power is not a
>>> multiple of 41.
>>> In addition when working with numbers larger that this and with the
>>> mod operator R crashes randomly.
>>
>> Could you keep a record of the random crashes, and see if you can make
>> any of them repeatable?  R shouldn't crash.  If you can find a
>> repeatable way to make it crash, then that's a bug that needs to be
>> fixed.  (If it crashes at random it should still be fixed, but it's so
>> much harder to fix that it's unlikely to happen unless the cases are
>> ones that look likely to come up in normal situations.)
>>
>>
>>>
>>> I believe this is because R stores large integers as real numbers
>>> thus there may be lack of accuracy when applying the modulus operator
>>> and converting back to integers.
>>>
>>> So my question is this: Is it possible to increase the size of memory
>>> used for storing integers? Say from 32 bits to 512 bits (Typical size
>>> of integers in cryptography).
>>
>> No, but there is at least one contributed package that does multiple
>> precision integer arithmetic.  I can't remember the name of it right
>> now, but Google should be able to find it for you...
>>
>> Duncan Murdoch
>>>
>>> Thank you, any help would be greatly appreciated.
>>> Ionut Florescu
>>>
>>> ______________________________________________
>>> [hidden email] mailing list
>>> https://stat.ethz.ch/mailman/listinfo/r-help
>>> PLEASE do read the posting guide!
>>> http://www.R-project.org/posting-guide.html
>>
>>

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: Integer bit size and the modulus operator

jholtman
In reply to this post by Ionut Florescu
The other thing that you have to be aware of is that 8^n is not 8 multiplied
by itself n times.  You are probably using logs to compute this.  Here is a
sample of 8^(1:20). The value of 8^2 is 64.000000000000004 (not exactly an
integer); roundoff errors are apparent in the other values.

> 8^(1:20)
 [1] 8.0000000000000000e+00 6.4000000000000004e+01 5.1200000000000001e+02
4.0960000000000001e+03
 [5] 3.2768000000000002e+04 2.6214400000000002e+05 2.0971519999999999e+06
1.6777215999999999e+07
 [9] 1.3421772800000000e+08 1.0737418240000001e+09 8.5899345920000005e+09
6.8719476736000003e+10
[13] 5.4975581388799997e+11 4.3980465111039999e+12 3.5184372088832001e+13
2.8147497671065600e+14
[17] 2.2517998136852482e+15 1.8014398509481984e+16 1.4411518807585588e+17
1.1529215046068471e+18
>

On 1/30/06, Ionut Florescu <[hidden email]> wrote:

>
> I am a statistician and I come up to an interesting problem in
> cryptography. I would like to use R since there are some statistical
> procedures that I need to use.
> However, I run into a problem when using the modulus operator %%.
>
> I am using R 2.2.1 and when I calculate modulus for large numbers (that
> I need with my problem) R gives me warnings. For instance if one does:
> a=1:40;
> 8^a %% 41
> one obtains zeros which is not possible since 8 to any power is not a
> multiple of 41.
> In addition when working with numbers larger that this and with the mod
> operator R crashes randomly.
>
> I believe this is because R stores large integers as real numbers thus
> there may be lack of accuracy when applying the modulus operator and
> converting back to integers.
>
> So my question is this: Is it possible to increase the size of memory
> used for storing integers? Say from 32 bits to 512 bits (Typical size of
> integers in cryptography).
>
> Thank you, any help would be greatly appreciated.
> Ionut Florescu
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide!
> http://www.R-project.org/posting-guide.html
>



--
Jim Holtman
Cincinnati, OH
+1 513 247 0281

What the problem you are trying to solve?

        [[alternative HTML version deleted]]

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: Integer bit size and the modulus operator

Brian Ripley
In reply to this post by Ionut Florescu
This is a double protection error in real_binary.  See the R-devel list
for the details.  Now fixed.

On Mon, 30 Jan 2006, Ionut Florescu wrote:

> Thank you for the quick reply, I will look into the R packages.
> For crashing R try this:
>
> generator.zp=function(x,p)
> {a=1:(p-1); b=x^a%%p;
> if(all(b[1:(p-2)]!=1)&&(b[p-1]==1)){return(x, " Good ")}
> else{return(x, " No Good, try another integer ")}
> }
>
> This checks if element x is a generator of the group Z_p. If you try
> this function for p = 41 and x various increasing values eventually it
> will crash R. That is what I meant by random, at first I started x=2,3
> so on, when I got to 8, R crashed. Now apparently I can get to 15. When
> I tried again I got to 20.
>
> Ionut Florescu
>
>
> Duncan Murdoch wrote:
>> On 1/30/2006 11:32 AM, Ionut Florescu wrote:
>>> I am a statistician and I come up to an interesting problem in
>>> cryptography. I would like to use R since there are some statistical
>>> procedures that I need to use.
>>> However, I run into a problem when using the modulus operator %%.
>>>
>>> I am using R 2.2.1 and when I calculate modulus for large numbers
>>> (that I need with my problem) R gives me warnings. For instance if
>>> one does:
>>> a=1:40;
>>> 8^a %% 41
>>> one obtains zeros which is not possible since 8 to any power is not a
>>> multiple of 41.
>>> In addition when working with numbers larger that this and with the
>>> mod operator R crashes randomly.
>>
>> Could you keep a record of the random crashes, and see if you can make
>> any of them repeatable?  R shouldn't crash.  If you can find a
>> repeatable way to make it crash, then that's a bug that needs to be
>> fixed.  (If it crashes at random it should still be fixed, but it's so
>> much harder to fix that it's unlikely to happen unless the cases are
>> ones that look likely to come up in normal situations.)
>>
>>
>>>
>>> I believe this is because R stores large integers as real numbers
>>> thus there may be lack of accuracy when applying the modulus operator
>>> and converting back to integers.
>>>
>>> So my question is this: Is it possible to increase the size of memory
>>> used for storing integers? Say from 32 bits to 512 bits (Typical size
>>> of integers in cryptography).
>>
>> No, but there is at least one contributed package that does multiple
>> precision integer arithmetic.  I can't remember the name of it right
>> now, but Google should be able to find it for you...
>>
>> Duncan Murdoch
>>>
>>> Thank you, any help would be greatly appreciated.
>>> Ionut Florescu
>>>
>>> ______________________________________________
>>> [hidden email] mailing list
>>> https://stat.ethz.ch/mailman/listinfo/r-help
>>> PLEASE do read the posting guide!
>>> http://www.R-project.org/posting-guide.html
>>
>>
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
>

--
Brian D. Ripley,                  [hidden email]
Professor of Applied Statistics,  http://www.stats.ox.ac.uk/~ripley/
University of Oxford,             Tel:  +44 1865 272861 (self)
1 South Parks Road,                     +44 1865 272866 (PA)
Oxford OX1 3TG, UK                Fax:  +44 1865 272595

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: Integer bit size and the modulus operator

Ionut Florescu
In reply to this post by jholtman
Thank you, I didn't notice that. I may have to come up with my own power
function as well, slower but precise.


jim holtman wrote:

> The other thing that you have to be aware of is that 8^n is not 8
> multiplied by itself n times.  You are probably using logs to compute
> this.  Here is a sample of 8^(1:20). The value of 8^2
> is 64.000000000000004 (not exactly an integer); roundoff errors are
> apparent in the other values.
>  
> > 8^(1:20)
>  [1] 8.0000000000000000e+00 6.4000000000000004e+01
> 5.1200000000000001e+02 4.0960000000000001e+03
>  [5] 3.2768000000000002e+04 2.6214400000000002e+05
> 2.0971519999999999e+06 1.6777215999999999e+07
>  [9] 1.3421772800000000e+08 1.0737418240000001e+09
> 8.5899345920000005e+09 6.8719476736000003e+10
> [13] 5.4975581388799997e+11 4.3980465111039999e+12
> 3.5184372088832001e+13 2.8147497671065600e+14
> [17] 2.2517998136852482e+15 1.8014398509481984e+16
> 1.4411518807585588e+17 1.1529215046068471e+18
> >
>  
> On 1/30/06, *Ionut Florescu* <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     I am a statistician and I come up to an interesting problem in
>     cryptography. I would like to use R since there are some statistical
>     procedures that I need to use.
>     However, I run into a problem when using the modulus operator %%.
>
>     I am using R 2.2.1 and when I calculate modulus for large numbers
>     (that
>     I need with my problem) R gives me warnings. For instance if one
>     does:
>     a=1:40;
>     8^a %% 41
>     one obtains zeros which is not possible since 8 to any power is not a
>     multiple of 41.
>     In addition when working with numbers larger that this and with
>     the mod
>     operator R crashes randomly.
>
>     I believe this is because R stores large integers as real numbers thus
>     there may be lack of accuracy when applying the modulus operator and
>     converting back to integers.
>
>     So my question is this: Is it possible to increase the size of memory
>     used for storing integers? Say from 32 bits to 512 bits (Typical
>     size of
>     integers in cryptography).
>
>     Thank you, any help would be greatly appreciated.
>     Ionut Florescu
>
>     ______________________________________________
>     [hidden email] <mailto:[hidden email]> mailing
>     list
>     https://stat.ethz.ch/mailman/listinfo/r-help
>     PLEASE do read the posting guide!
>     http://www.R-project.org/posting-guide.html
>
>
>
>
> --
> Jim Holtman
> Cincinnati, OH
> +1 513 247 0281
>
> What the problem you are trying to solve?

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: Integer bit size and the modulus operator

Peter Dalgaard
In reply to this post by jholtman
jim holtman <[hidden email]> writes:

> The other thing that you have to be aware of is that 8^n is not 8 multiplied
> by itself n times.  You are probably using logs to compute this.  Here is a
> sample of 8^(1:20). The value of 8^2 is 64.000000000000004 (not exactly an
> integer); roundoff errors are apparent in the other values.
>
> > 8^(1:20)
>  [1] 8.0000000000000000e+00 6.4000000000000004e+01 5.1200000000000001e+02
> 4.0960000000000001e+03
>  [5] 3.2768000000000002e+04 2.6214400000000002e+05 2.0971519999999999e+06
> 1.6777215999999999e+07
>  [9] 1.3421772800000000e+08 1.0737418240000001e+09 8.5899345920000005e+09
> 6.8719476736000003e+10
> [13] 5.4975581388799997e+11 4.3980465111039999e+12 3.5184372088832001e+13
> 2.8147497671065600e+14
> [17] 2.2517998136852482e+15 1.8014398509481984e+16 1.4411518807585588e+17
> 1.1529215046068471e+18

This was resolved a few versions back as I recall it (seems to have
eluded the NEWS file?):

> options(digits=20)
> 8^(1:20)
 [1] 8.0000000000000000000e+00 6.4000000000000000000e+01
 [3] 5.1200000000000000000e+02 4.0960000000000000000e+03
 [5] 3.2768000000000000000e+04 2.6214400000000000000e+05
 [7] 2.0971520000000000000e+06 1.6777216000000000000e+07
 [9] 1.3421772800000000000e+08 1.0737418240000000000e+09
[11] 8.5899345920000000000e+09 6.8719476736000000000e+10
[13] 5.4975581388800000000e+11 4.3980465111040000000e+12
[15] 3.5184372088832000000e+13 2.8147497671065600000e+14
[17] 2.2517998136852480000e+15 1.8014398509481984000e+16
[19] 1.4411518807585587200e+17 1.1529215046068469760e+18

> 8^(1:20) %%1
 [1] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Warning messages:
1: probable complete loss of accuracy in modulus
2: probable complete loss of accuracy in modulus
3: probable complete loss of accuracy in modulus


--
   O__  ---- Peter Dalgaard             Øster Farimagsgade 5, Entr.B
  c/ /'_ --- Dept. of Biostatistics     PO Box 2099, 1014 Cph. K
 (*) \(*) -- University of Copenhagen   Denmark          Ph:  (+45) 35327918
~~~~~~~~~~ - ([hidden email])                  FAX: (+45) 35327907

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: Integer bit size and the modulus operator

Ionut Florescu
Actually it does that in my 2.2.1 version as well:

 > options(digits=20)
 > 8^(1:20)
 [1] 8.0000000000000000e+00 6.4000000000000004e+01 5.1200000000000001e+02
 [4] 4.0960000000000001e+03 3.2768000000000002e+04 2.6214400000000002e+05
 [7] 2.0971519999999999e+06 1.6777215999999999e+07 1.3421772800000000e+08
[10] 1.0737418240000001e+09 8.5899345920000005e+09 6.8719476736000003e+10
[13] 5.4975581388799997e+11 4.3980465111039999e+12 3.5184372088832001e+13
[16] 2.8147497671065600e+14 2.2517998136852482e+15 1.8014398509481984e+16
[19] 1.4411518807585588e+17 1.1529215046068471e+18



Peter Dalgaard wrote:

> jim holtman <[hidden email]> writes:
>
>  
>> The other thing that you have to be aware of is that 8^n is not 8 multiplied
>> by itself n times.  You are probably using logs to compute this.  Here is a
>> sample of 8^(1:20). The value of 8^2 is 64.000000000000004 (not exactly an
>> integer); roundoff errors are apparent in the other values.
>>
>>    
>>> 8^(1:20)
>>>      
>>  [1] 8.0000000000000000e+00 6.4000000000000004e+01 5.1200000000000001e+02
>> 4.0960000000000001e+03
>>  [5] 3.2768000000000002e+04 2.6214400000000002e+05 2.0971519999999999e+06
>> 1.6777215999999999e+07
>>  [9] 1.3421772800000000e+08 1.0737418240000001e+09 8.5899345920000005e+09
>> 6.8719476736000003e+10
>> [13] 5.4975581388799997e+11 4.3980465111039999e+12 3.5184372088832001e+13
>> 2.8147497671065600e+14
>> [17] 2.2517998136852482e+15 1.8014398509481984e+16 1.4411518807585588e+17
>> 1.1529215046068471e+18
>>    
>
> This was resolved a few versions back as I recall it (seems to have
> eluded the NEWS file?):
>
>  
>> options(digits=20)
>> 8^(1:20)
>>    
>  [1] 8.0000000000000000000e+00 6.4000000000000000000e+01
>  [3] 5.1200000000000000000e+02 4.0960000000000000000e+03
>  [5] 3.2768000000000000000e+04 2.6214400000000000000e+05
>  [7] 2.0971520000000000000e+06 1.6777216000000000000e+07
>  [9] 1.3421772800000000000e+08 1.0737418240000000000e+09
> [11] 8.5899345920000000000e+09 6.8719476736000000000e+10
> [13] 5.4975581388800000000e+11 4.3980465111040000000e+12
> [15] 3.5184372088832000000e+13 2.8147497671065600000e+14
> [17] 2.2517998136852480000e+15 1.8014398509481984000e+16
> [19] 1.4411518807585587200e+17 1.1529215046068469760e+18
>
>  
>> 8^(1:20) %%1
>>    
>  [1] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
> Warning messages:
> 1: probable complete loss of accuracy in modulus
> 2: probable complete loss of accuracy in modulus
> 3: probable complete loss of accuracy in modulus
>
>
>

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: Integer bit size and the modulus operator

Peter Dalgaard
Ionut Florescu <[hidden email]> writes:

> Actually it does that in my 2.2.1 version as well:
>
>  > options(digits=20)
>  > 8^(1:20)
>  [1] 8.0000000000000000e+00 6.4000000000000004e+01 5.1200000000000001e+02
>  [4] 4.0960000000000001e+03 3.2768000000000002e+04 2.6214400000000002e+05
>  [7] 2.0971519999999999e+06 1.6777215999999999e+07 1.3421772800000000e+08
> [10] 1.0737418240000001e+09 8.5899345920000005e+09 6.8719476736000003e+10
> [13] 5.4975581388799997e+11 4.3980465111039999e+12 3.5184372088832001e+13
> [16] 2.8147497671065600e+14 2.2517998136852482e+15 1.8014398509481984e+16
> [19] 1.4411518807585588e+17 1.1529215046068471e+18
>

Hmm, then it is a platform dependency and my memory playing tricks on
me... The thing that got fixed was log2(8), perhaps?
 

--
   O__  ---- Peter Dalgaard             Øster Farimagsgade 5, Entr.B
  c/ /'_ --- Dept. of Biostatistics     PO Box 2099, 1014 Cph. K
 (*) \(*) -- University of Copenhagen   Denmark          Ph:  (+45) 35327918
~~~~~~~~~~ - ([hidden email])                  FAX: (+45) 35327907

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
Reply | Threaded
Open this post in threaded view
|

Re: Integer bit size and the modulus operator

Brian Ripley
On Mon, 30 Jan 2006, Peter Dalgaard wrote:

> Ionut Florescu <[hidden email]> writes:
>
>> Actually it does that in my 2.2.1 version as well:
>>
>> > options(digits=20)
>> > 8^(1:20)
>>  [1] 8.0000000000000000e+00 6.4000000000000004e+01 5.1200000000000001e+02
>>  [4] 4.0960000000000001e+03 3.2768000000000002e+04 2.6214400000000002e+05
>>  [7] 2.0971519999999999e+06 1.6777215999999999e+07 1.3421772800000000e+08
>> [10] 1.0737418240000001e+09 8.5899345920000005e+09 6.8719476736000003e+10
>> [13] 5.4975581388799997e+11 4.3980465111039999e+12 3.5184372088832001e+13
>> [16] 2.8147497671065600e+14 2.2517998136852482e+15 1.8014398509481984e+16
>> [19] 1.4411518807585588e+17 1.1529215046068471e+18
>>
>
> Hmm, then it is a platform dependency and my memory playing tricks on
> me... The thing that got fixed was log2(8), perhaps?

It is platform dependent, as it basically uses the system's pow()
function.  That almost certainly does not use logs.

However, the results above are the result of printing digits that do not
exist, and reflect the platforms printf() function.  They look like the
results on Windows, where e.g.

> 8^7 - 2097152
[1] 0
> 8^(1:20) %% 1
  [1] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Warning messages:
1: probable complete loss of accuracy in modulus
2: probable complete loss of accuracy in modulus
3: probable complete loss of accuracy in modulus

despite the discrepancies shown in the printout.

BTW, pow() on Windows was replaced a while back and is the same code as
glibc on ix86 Linux.

So two morals:

1) Do not ignore warnings
2) Distinguish between results and their printed representation.

--
Brian D. Ripley,                  [hidden email]
Professor of Applied Statistics,  http://www.stats.ox.ac.uk/~ripley/
University of Oxford,             Tel:  +44 1865 272861 (self)
1 South Parks Road,                     +44 1865 272866 (PA)
Oxford OX1 3TG, UK                Fax:  +44 1865 272595

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html