high centroid frequency causes overflow - giving incorrect results

[rohancs]

See sample code. When centroid frequency goes into billions and approaches INT.MAX_VALUE, quantile method seems to go through an overflow and reports incorrect result.

Data-structure state seems to be consistent - but when evaluating quantile, incorrect results get returned.

[https://github.com/rohancs/t-digest-bug/blob/master/src/main/java/TDigestBug.java]

[tdunning]

Thanks Rohan!

…

On Tue, Jul 25, 2017 at 11:52 AM, Rohan Sharma ***@***.***> wrote: See sample code. When centroid frequency goes into billions and approaches INT.MAX_VALUE, quantile method seems to go through an overflow and reports incorrect result. Data-structure state seems to be consistent - but when evaluating quantile, incorrect results get returned. [https://github.com/rohancs/t-digest-bug/blob/master/src/ main/java/TDigestBug.java] — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#93>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAPSet91royyb89llG5FWQSe3LWmd7Swks5sRjl2gaJpZM4Oi-ZH> .

[tdunning]

@rohancs Did you have a proposed fix?

I am getting ready for a release.

[tdunning]

@rohancs

I ran your code on the master branch. I don't understand the problem or it has been fixed. I get this output from your code:

/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/bin/java -Didea.launcher.port=7533 "-Didea.launcher.bin.path=/Applications/IntelliJ IDEA.app/Contents/bin" -Dfile.encoding=UTF-8 -classpath "/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/lib/ant-javafx.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/lib/dt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/lib/javafx-mx.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/lib/jconsole.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/lib/packager.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/lib/sa-jdi.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/lib/tools.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/jre/lib/charsets.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/jre/lib/deploy.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/jre/lib/javaws.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/jre/lib/jce.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/jre/lib/jfr.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/jre/lib/jfxswt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/jre/lib/jsse.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/jre/lib/management-agent.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/jre/lib/plugin.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/jre/lib/resources.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/jre/lib/rt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/jre/lib/ext/cldrdata.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/jre/lib/ext/dnsns.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/jre/lib/ext/jfxrt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/jre/lib/ext/localedata.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/jre/lib/ext/nashorn.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/jre/lib/ext/sunec.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/jre/lib/ext/sunjce_provider.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/jre/lib/ext/sunpkcs11.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_40.jdk/Contents/Home/jre/lib/ext/zipfs.jar:/Users/tdunning/Apache/t-digest/target/test-classes:/Users/tdunning/Apache/t-digest/target/classes:/Library/Python/2.7/site-packages/rope-0.9.3-py2.7.egg:/Library/Python/2.7/site-packages/ropemode-0.1_rc2-py2.7.egg:/Library/Python/2.7/site-packages/ropemacs-0.6-py2.7.egg:/Library/Python/2.7/site-packages/readline-6.2.2-py2.7-macosx-10.7-intel.egg:/Library/Python/2.7/site-packages/paramiko-1.9.0-py2.7.egg:/Library/Python/2.7/site-packages/pycrypto-2.6-py2.7-macosx-10.7-intel.egg:/Library/Python/2.7/site-packages/PyYAML-3.10-py2.7-macosx-10.7-intel.egg:/Library/Python/2.7/site-packages/carbon-0.9.10-py2.7.egg:/Library/Python/2.7/site-packages/txAMQP-0.6.1-py2.7.egg:/Library/Python/2.7/site-packages/whisper-0.9.10-py2.7.egg:/Library/Python/2.7/site-packages/graphite_web-0.9.10-py2.7.egg:/Library/Python/2.7/site-packages/parquet-1.0-py2.7.egg:/Library/Python/2.7/site-packages:/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7:/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/plat-darwin:/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/plat-mac:/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/plat-mac/lib-scriptpackages:/System/Library/Frameworks/Python.framework/Versions/2.7/Extras/lib/python:/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/lib-tk:/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/lib-dynload:/System/Library/Frameworks/Python.framework/Versions/2.7/Extras/lib/python/PyObjC:/Users/tdunning/Library/Application Support/IntelliJIdea2016.3/python/helpers/python-skeletons:/Users/tdunning/.m2/repository/org/apache/mahout/mahout-math/0.9/mahout-math-0.9.jar:/Users/tdunning/.m2/repository/org/apache/commons/commons-math3/3.2/commons-math3-3.2.jar:/Users/tdunning/.m2/repository/org/slf4j/slf4j-api/1.7.5/slf4j-api-1.7.5.jar:/Users/tdunning/.m2/repository/com/clearspring/analytics/stream/2.5.2/stream-2.5.2.jar:/Users/tdunning/.m2/repository/it/unimi/dsi/fastutil/6.5.7/fastutil-6.5.7.jar:/Users/tdunning/.m2/repository/com/carrotsearch/randomizedtesting/randomizedtesting-runner/2.1.11/randomizedtesting-runner-2.1.11.jar:/Users/tdunning/.m2/repository/junit/junit/4.10/junit-4.10.jar:/Users/tdunning/.m2/repository/com/carrotsearch/java-sizeof/0.0.5/java-sizeof-0.0.5.jar:/Users/tdunning/.m2/repository/org/apache/commons/commons-lang3/3.4/commons-lang3-3.4.jar:/Users/tdunning/.m2/repository/com/google/guava/guava/19.0/guava-19.0.jar:/Applications/IntelliJ IDEA.app/Contents/lib/idea_rt.jar" com.intellij.rt.execution.application.AppMain com.tdunning.math.stats.BigCountTest
******Iteration 1: ******
Count = 1500000200	 Median = 3000.0003333333334
******Iteration 2: ******
Count = 3000000400	 Median = 3000.0
******Iteration 3: ******
Count = 4500000600	 Median = 3000.0
******Iteration 4: ******
Count = 6000000800	 Median = 3000.0
******Iteration 5: ******
Count = 7500001000	 Median = 3000.0

This seems OK to me. Can you comment?

[rohancs]

Hi @tdunning - sorry i was out on vacation and just got back. You are right - looks like this is fixed in the current master. My test was pinned against your last release version 3.1

[tdunning]

That's great new. I will resolve this issue and not block the next release.

…

On Thu, Aug 3, 2017 at 12:52 PM, Rohan Sharma ***@***.***> wrote: Hi @tdunning <https://github.com/tdunning> - sorry i was out on vacation and just got back. You are right - looks like this is fixed in the current master. My test was pinned against your last release version 3.1 — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#93 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAPSegr6B1PsB4aFsNxRNTqrCTFtUxodks5sUiT2gaJpZM4Oi-ZH> .

[rohancs]

sounds good. Thank you !