标签: integer-arithmetic

我有一个数学问题,包括两个问题:

• 我们能找到一个N只能知道其平方根的小数部分,直到精度(只是小数部分的近似值,因为小数部分永远不会结束)
• 答案是独特的吗？这意味着我们找不到两个平方根十进制值相等的整数(例如前50个).

例:

如果我们有0,4142135623730950488016887242097,我们能否发现它是2的平方根的小数部分或0,418286444621616658231167581对于1234567890第二个问题的答案很简单,因为,假设我们有50个小数,可能的整数的平方数root远远超过小数部分的10 ^ 50-1可能值,因此不止一个答案.

我非常感谢您的帮助或任何研究课程.

OpenBSD的C库有一个名为reallocarray(3)的扩展realloc(array, size*nmemb),如果乘法溢出,它就不会爆炸. 该实现包含此片段:

/*
 * This is sqrt(SIZE_MAX+1), as s1*s2 <= SIZE_MAX
 * if both s1 < MUL_NO_OVERFLOW and s2 < MUL_NO_OVERFLOW
 */
#define MUL_NO_OVERFLOW (1UL << (sizeof(size_t) * 4))

在Programmers.SE上,该计算的修改版本因技术错误而受到谴责. 4显然应该是CHAR_BIT/2,但这不是唯一的问题.假设一个不常见的ABI,其中size_t有填充位.(这并非荒谬地令人难以置信:考虑一个具有32位寄存器但具有24位地址空间的微控制器.)然后SIZE_MAX小于1 << (sizeof(size_t)*CHAR_BIT)[在无限精度算术中]并且计算错误.

所以,问题:你能否floor(sqrt(SIZE_MAX+1))仅使用C99整数常数表达式算法进行计算,除了C99要求以及你可以从中学到什么之外,不做任何关于ABI的假设<limits.h>？注意,SIZE_MAX可能相等UINTMAX_MAX,即可能没有任何类型可以表示SIZE_MAX+1没有溢出.

编辑:我认为 SIZE_MAX需要为2 ^ñ  - 1为正整数Ñ,但不必然是形式2的^2n个  - 1 -考虑S/390中,一个其的的ABI有一个31位的地址空间.因此:如果sqrt(SIZE_MAX+1) …

我写了以下内容来帮助大孩子们完成他们的家庭教育工作,并通过学习如何编程来保持思维工作(我认为haskell听起来很棒).

main :: IO ()
main = do
   putStrLn "Please enter the dividend :"
   inputx  <- getLine
   putStrLn "Please enter the divisor :"
   inputy  <- getLine
   let x = (read inputx) :: Int
   let y = (read inputy) :: Int
   let z = x `div` y
   let remain = x `mod` y
   putStrLn ( "Result: " ++ show x ++ " / " ++ show y ++ " =  " ++ show z ++  " remainder " ++ show remain …

我的代码中有一个表达式 -
int i = 10 + + 11 - - 12 + + 13 - - 14 + + 15;
变量'i'的值计算为75,这是表达式中提到的所有整数的总和.在这种情况下评估是如何进行的？

我正在开发一个只有整数运算的平台.应用程序使用地理信息,我用(x,y)坐标表示点,其中x和y是以米为单位测量的距离.作为近似,我想计算两点之间的欧几里德距离.但要做到这一点,我必须平方距离,并使用32位整数,我可以代表的最大距离是32公里.不好.我的需求更多的是1000公里.但我希望能够在小于30米的范围内解决距离问题.

因此我的问题是:我如何计算欧几里德距离,只使用整数运算,没有溢出,对于正方形不适合单个单词的距离？

ETA:我希望能够计算距离,但我可能会满足于能够比较它们.

什么是最快的实施方式

template <typename T>
unsigned highest_decimal_digit(T x);

(返回例如3表示356431,7表示71表示,9表示9表示)？

我能想到的最好的是:

• constexpr-计算适合T的"中等大小"10的幂.
• 执行二进制搜索(超过10的幂,可能使用constexpr构造的查找表)来找到p,10的最高功率低于x.
• 返回x除以p

......但也许有另一种方法.

笔记:

• 我用C++ 14ish术语表达了问题和我的方法,并且代码中的解决方案会很好,但是抽象解决方案(甚至是x86_64汇编中的解决方案)都可以.我确实想要一些适用于所有(无符号)整数类型的东西.
• 您可以忽略有符号整数类型.
• 我没有说明"快"是什么,但请注意硬件.

在信号处理许多无损算法需要的形式⌊的表达的评估  一个  / 2 ^b  ⌋,其中一个,b是签名(一个可能为负,b非负)的整数和⌊·⌋是地板函数.这通常会导致以下实施.

int floor_div_pow2(int numerator, int log2_denominator)
{
    return numerator >> log2_denominator;
}

不幸的是,C标准规定>>如果左操作数具有有符号类型和负值,则运算符的结果是实现定义的.

为了确保所有平台上的正确行为,可以用多个if-else条件替换这个简单的函数,从而导致程序性能不佳.(必须有人来治疗的整数溢出和考虑的情况下,当numerator为INT_MIN.)

因此,我想问一下,在C中实现算术右移的最佳实践是什么？理想情况下,我正在寻找与上面的代码片段编译成相同代码¹的构造,同时避免实现定义的行为.

¹考虑例如gcc和x86-64平台

更新:

经过一番思考,我意识到我在上面的问题中做了不正确的暗示.如果平台不使用二进制补码,则使用算术移位计算负数的基函数是没有意义的.我们的目标是实现表达⌊  一个  / 2 ^b  ⌋在便携式方式.

为什么Rust的u64原始u32函数期望指数？

error[E0308]: mismatched types
  --> src/protagonists.rs:13:25
   |
13 |         return root.pow(self.secret) % prime;
   |                         ^^^^^^^^^^^ expected u32, found u64
help: you can convert an `u64` to `u32` and panic if the converted value wouldn't fit

https://doc.rust-lang.org/std/primitive.u64.html#pow.v

我在Lisp教科书中读到这篇文章:

Lisp可以用数字执行一些惊人的壮举,特别是与大多数其他语言相比时.例如,这里我们使用函数expt来计算53的53的幂:

CL> (expt 53 53) 
24356848165022712132477606520104725518533453128685640844505130879576720609150223301256150373

大多数语言会在涉及如此大数目的计算中窒息.

是的,这很酷,但作者没有解释为什么Lisp可以比其他语言更容易,更快地完成这项工作.

当然有一个简单的原因,任何人都可以解释一下吗？

我想知道 x**2 还是 x*x 更快

def sqr(x):
    for i in range (20):
        x = x**2
    return x
def sqr_(x):
    for i in range (20):
        x = x*x
    return x

当我计时时，这就是我得到的：

The time it takes for x**2: 101230500
The time it takes for x*x: 201469200

我已经尝试了很多很多次，它们要么相等，要么 x ** 2 比 x * x 快。但 x*x 永远不会比 x**2 快。

所以我反驳了代码：

对于 x**2：

  5          12 LOAD_FAST                0 (x)
             14 LOAD_CONST               2 (2)
             16 BINARY_POWER
             18 STORE_FAST               0 (x)
             20 JUMP_ABSOLUTE            8

对于 x*x： …