c++ - 为什么在评估多项式时horners方法没有溢出

问题描述

评估多项式

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

我正在评估多项式，并且我正在使用天真的方法评估多项式的天真方法是逐项评估所有项。首先计算 x^n，将该值与 cn 相乘，对其他项重复相同的步骤并返回总和。使用以下算法

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，而在朴素方法中存在溢出。在这两种方法中，我都使用 mod 运算符来避免溢出，所以在幼稚的方法中也不应该溢出。
我天真的方法返回错误的哈希值？我调试但不确定为什么我得到错误的值。例如，“世界”的哈希值为 4，但天真的方法返回 1。什么是错误？

谢谢您的帮助。

标签： c++algorithmhashpolynomials

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

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

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

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

c++ - 为什么在评估多项式时horners方法没有溢出

问题描述

解决方案

推荐阅读