我正在编写一种编程语言,今天我得到了可以编译阶乘函数(递归)的点,但是由于整数的最大值,我能得到的最大值是阶乘(12).什么是处理任意最大大小的整数的技术.该语言目前通过将代码转换为C++来工作.
所以我最近一直在努力实施Miller-Rabin素性测试.我将它限制在所有32位数字的范围内,因为这是一个非常有趣的项目,我正在做的是熟悉c ++,我不想使用64位的任何东西.一会儿.另外一个好处是该算法对于所有32位数字都是确定性的,因此我可以显着提高效率,因为我确切知道要测试的证人.
因此对于较低的数字,该算法工作得非常好.但是,该过程的一部分依赖于模幂运算,即(num ^ pow)%mod.所以,例如,
3 ^ 2 % 5 =
9 % 5 =
4
这是我用于此模幂运算的代码:
unsigned mod_pow(unsigned num, unsigned pow, unsigned mod)
{
unsigned test;
for(test = 1; pow; pow >>= 1)
{
if (pow & 1)
test = (test * num) % mod;
num = (num * num) % mod;
}
return test;
}
正如您可能已经猜到的那样,当参数都是特别大的数字时会出现问题.例如,如果我想测试数字673109的素数,我将在某一点上必须找到:
(2 ^ 168277)%673109
现在2 ^ 168277是一个特别大的数字,并且在过程的某个地方它溢出测试,这导致不正确的评估.
在反面,诸如的论点
4000111222 ^ 3%1608
由于同样的原因,也评估不正确.
有没有人对模块取幂有一些建议,可以防止这种溢出和/或操纵它产生正确的结果？(我看到它的方式,溢出只是模数的另一种形式,即num%(UINT_MAX + 1))
令我震惊的是,以下代码将在没有警告的情况下编译:
public void test()
{
int value = 2000000000;
long increment = 1000000000;
value += increment;
}
虽然这会产生编译时错误,正如您所期望的那样:
public void test()
{
int value = 2000000000;
long increment = 1000000000;
value = value + increment;
}
我检查了一下,事实上,JLS(第15.26.2节)有这样的说法:
形式E1 op = E2的复合赋值表达式等效于E1 =(T)((E1)op(E2)),其中T是E1的类型,除了E1仅被评估一次.
这对我来说似乎很荒谬.为什么他们觉得有必要在这里明确投射？似乎自动类型转换无论如何都会处理扩展,并且像这样自动缩小几乎可以保证导致整数溢出.
我知道java.lang.Math中提供了一组静态方法来执行某些操作(sum,difference,multiply,increment,decrement,negate,toInt),抛出ArithmeticException溢出.
电力有类似的东西吗？
在C和C++中,未定义有符号整数上溢或下溢的行为.
在Java和C#(未经检查的上下文)中,行为似乎在某种程度上被定义.
从Java规范,我们有:
整数运算符不以任何方式指示上溢或下溢.
和:
Java编程语言对整数使用二进制补码表示[...]
从C#规范,我们有:
[...]在未经检查的上下文中,忽略溢出,并且丢弃不适合目标类型的任何高位.
通过测试两者,我得到了预期的环绕结果.从规范的措辞来看,我感觉在Java中结果是可移植的(因为语言需要2的补码表示),而C#可能有也可能没有结果(因为它似乎没有指定表示 - 只有高阶位被丢弃).
那么,两种语言规范是否都能在所有平台上保证相同的行为(只是用不同的措辞)？或者他们在我的测试用例中(在x86上和Sun的JRE和Microsoft的.NET下)恰好相同,但理论上在其他架构或实现方面可能有所不同吗？
我的程序经常需要执行以下计算：
鉴于：
找：
显然我可以直接使用r=x*n/d，但经常会从中溢出x*n。如果我改为这样做，r=x*(n/d)则由于整数除法会除去小数部分，因此我只会得到0或x。然后有，r=x*(float(n)/d)但在这种情况下我不能使用浮点数。
精度会很高，但并不像速度和决定性功能那么关键（总是在给定相同输入的情况下返回相同的值）。
N和D当前已签名，但如果有帮助，我可以解决它们始终未签名的问题。
可以使用任何X值（以及N和D，只要N <= D）的泛型函数是理想的，因为此操作以各种不同的方式使用，但是我也有一个特殊的情况，其中X的值是已知的保持2的幂（准确地说是2048），并且加快特定的调用速度将是一个很大的帮助。
目前，我正在使用64位乘法和除法来完成此操作，以避免溢出（本质上是，int multByProperFraction(int x, int n, int d) { return (__int64)x * n / d; }但是有一些断言和多余的位数摆弄而不是舍入）。
不幸的是，我的探查器报告64位除法函数占用了过多的CPU（这是一个32位应用程序）。我尝试减少执行此计算的频率，但用尽了很多方法，因此，即使有可能，我也在尝试找出一种更快的方法。在X的常数为2048的特定情况下，我使用了移位而不是乘法，但这并没有太大帮助。
我需要处理一个计数器,它为我的应用程序提供了滴答声.计数器是32位,所以我需要知道的是如何在它包装时处理它.例如:
我有一个函数返回一个(timestamp + shifttime),我有另一个函数将返回1或0取决于时间是否已经过去,但我的计数器可能会包装如何处理这个？ .
谢谢
非常感谢所有回复的人.我将在此编辑中提供更多详细信息.
我使用的是STM32 Cortex-M3.我想使用RTC计数器将其用作我的应用程序的滴答,以安排需要以特定间隔发生的任务.RTC可以产生溢出中断,因此检测中断不是问题.我遇到的主要问题(或者至少我认为是一个问题)是某些任务获得(时间戳+班次),即.
int main( void )
{
FlashLedTimeStamp = ReturnCounter( 20 ); // currentcounter value + a shift of 20
StatusLedTimeStamp = ReturnCounter( 3 ); // currentcounter value + a shift of 3
//then later on ....
while(1)
{
/* other tasks could go here */
if( HasTimeElapsed( FlashLedTimeStamp );
{
/* do something and get another timestamp value */
FlashLedTimeStamp = ReturnCounter( 20 ); // currentcounter value + a shift of 20 …考虑一个典型的绝对值函数(为了参数,最大大小的整数类型很长):
unsigned long abs(long input);
这种天真的实现可能看起来像:
unsigned long abs(long input)
{
if (input >= 0)
{
// input is positive
// We know this is safe, because the maximum positive signed
// integer is always less than the maximum positive unsigned one
return static_cast<unsigned long>(input);
}
else
{
return static_cast<unsigned long>(-input); // ut oh...
}
}
此代码触发未定义的行为,因为否定input可能溢出,并且触发有符号整数溢出是未定义的行为.例如,在2s补码机器上,绝对值std::numeric_limits<long>::min()将大于1 std::numeric_limits<long>::max().
图书馆作者可以做些什么来解决这个问题？
当我在工作时,string::npos我注意到了一些东西,我在网上找不到任何解释.
(string::npos == ULONG_MAX)
和
(string::npos == -1)
是真的.
所以我尝试了这个:
(18446744073709551615 == -1)
这也是事实.
怎么可能？是因为二元对话吗？
我想获得在c中添加两个无符号64位整数的进位位。如果需要，我可以使用x86-64 asm。码：
#include <stdio.h>
typedef unsigned long long llu;
int main(void){
llu a = -1, b = -1;
int carry = /*carry of a+b*/;
llu res = a+b;
printf("a+b = %llu (because addition overflowed), carry bit = %d\n", res, carry);
return 0;
}