为什么在计算多项式时霍纳斯方法没有溢出

Question

计算多项式

基本上我是使用以下公式计算字符串的哈希值。

我正在评估多项式，我正在使用朴素方法评估多项式的一种天真的方法是逐项评估所有项。先计算x^n，乘以cn，其他项重复相同步骤return求和。使用以下算法

struct hashFunction {
    std::size_t operator() (const std::string& str) const {

        unsigned int uiHashValue     = 0;
        unsigned int uiPowerValueIdx = 0;
        std::uint64_t uiSum          = 0;
        for(unsigned int uiIdx = 0; uiIdx < str.length(); uiIdx++, uiPowerValueIdx++) {

            unsigned int uiCharAsciiVal = (str[uiIdx]);
            // calculate power of x ^ uiPowerValue
            std::uint64_t uiXToPowerValue     = 1;
            std::uint64_t uiIntermediateValue = uiXValue;
            unsigned int uiPowerValue        =  uiPowerValueIdx;
            std::cout << uiIdx << " char is " << str[uiIdx] << " ascii value " << uiCharAsciiVal ;
            while(uiPowerValue > 0) {
                // if power value is multiply x value with intermediate value
                if((uiPowerValue & 1) == 1) {
                    uiXToPowerValue = ((uiXToPowerValue % uiLargePrime) * (uiIntermediateValue %uiLargePrime)) %uiLargePrime ;
                }
                uiPowerValue = uiPowerValue >> 1;
                uiIntermediateValue = ((uiIntermediateValue % uiLargePrime) * (uiIntermediateValue % uiLargePrime)) % uiLargePrime;
            }
            std::cout << " power value " << uiXToPowerValue<< std::endl;
            uiSum = uiSum + (((uiCharAsciiVal % uiLargePrime )* (uiXToPowerValue % uiLargePrime)))%uiLargePrime;

        } // for loop

        std::cout << (uiSum % uiMValue) << std::endl;
        return uiSum % uiMValue;
    }
};

现在使用horners方法计算如下

struct hashFunctionNew {
    std::size_t operator() (const std::string& str) const {

        unsigned int uiHashValue     = 0;
        unsigned int uiPowerValueIdx = 0;
        std::uint64_t uiSum          = 0;
        std::uint64_t ans = 0;
        for( int uiIdx = str.length(); uiIdx >= 0; uiIdx--) {
            unsigned int uiCharAsciiVal = (str[uiIdx]);
             ans = (ans * uiXValue +uiCharAsciiVal) % uiLargePrime;
        }
        std::cout << "New function hash value: " << ans % uiMValue << std::endl;
        return ans % uiMValue;

    }
};

我的问题如下

为什么 Horners 方法没有溢出，尽管我们在这里也计算了 x^n，而在 naive 方法中有溢出。在这两种方法中，我都使用 mod 运算符来避免溢出，因此在天真的方法中也不应该溢出。
我天真的方法是return输入错误的散列值？我调试了但不确定为什么我得到错误的值。例如 "world" 的散列值是 4 但天真的方法 returns 1. 什么是错误？

感谢您的帮助。

Answer 1

这两个问题的答案都在这一行中：

uiSum = uiSum + (((uiCharAsciiVal % uiLargePrime )* (uiXToPowerValue % uiLargePrime)))%uiLargePrime;

这是发生溢出的地方。这里也需要取模。

uiSum = (uiSum + (((uiCharAsciiVal % uiLargePrime )* (uiXToPowerValue % uiLargePrime)))%uiLargePrime) % uiLargePrime;

为什么在计算多项式时霍纳斯方法没有溢出

why there is no overflow in horners method in evaluating polynomial

c++

algorithm

hash

polynomials