Comments (5)
It seems to be some kind of overflow of hashWord
/reHashWord
. With previous strings the computed hash is above Number.MAX_SAFE_INTEGER
.
Number.MAX_SAFE_INTEGER; //9007199254740991
hashWord(" !/'#'pp"); //9143038766935264
reHashWord(hashWord("^ !/'#'p"), "^ !/'#'p", " !/'#'pp"); //9143038766935266
Maybe we can try to mod the hash into [-2 ** 31, 2 ** 31 -1] space in order to get rid of the issue. I will give it a try and send you an update as soon as I get something.
from javascript-algorithms.
Given the fact that the issue is coming from word[charIndex].charCodeAt(0) * PRIME ** charIndex
going above Number.MAX_SAFE_INTEGER
, it means we are safe up to charIndex == 4
because 0x10ffff * 97 ** 4 < Number.MAX_SAFE_INTEGER
- false for 5.
The current implementation of the algorithm should be ok - will confirm my test passes with this limit - for any word having at most 5 characters otherwise there is no guarantee that it does not overflow and goes into rounding issues.
from javascript-algorithms.
Good catch @dubzzz
from javascript-algorithms.
@trekhleb Would you agree on a PR adding some property based tests in this repository?
All the issues I reported so far were found using this test method. For the moment I only added them for sorting, knuth and rabin in my local fork. I think I can spend some time to check the other algorithms too.
In a nutshell:
It is a testing approach complementary to examples based tests. The idea is to check for properties:
for all (x, y, ...) such as precondition(x, y, ...) holds property(x, y, ...) is true
The framework is then responsible to generate x,y..., such as precondition holds, run the check on them and build a smaller failing case in case of failure.
Running example: https://runkit.com/dubzzz/rabin
from javascript-algorithms.
from javascript-algorithms.
Related Issues (20)
- All-algorithms
- Изучить 2.
- Translation of documents to Urdu, Hindi & Roman-Urdu HOT 2
- NO code available for Longest Increasing Subsequence HOT 6
- How to use the repository HOT 2
- Add Animations to Algorithms
- Binary Search file, comment typo HOT 3
- JS Data structure And Algorithms HOT 1
- priorityQueue does not poll out as expected HOT 4
- Javadcript
- Typo in Portuguese README
- Data structures and algorithms by JavaScript
- Would be great to see `discussions` tab brought to this repository
- JavaScript HOT 3
- Traverse in Reverse is unnecessary complex HOT 4
- Unhandled Edge Case in Binary Search Implementation HOT 1
- `replaceChild` method in BinaryTreeNode is not correct HOT 1
- Pendekatan "Brute Force" dan "Divide and Conquer" HOT 1
- Why this pointing to global context is giving undefined, even when global variable is defined ? HOT 2
- is there support for support for `BigInt` HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from javascript-algorithms.