Hi,
Chris kindly searched collisions on his 6 TiB ram server and we could
not find any for more than 5 x 2^37 inputs (for both + and ^ versions)
! Final version of the hash is available at
https://github.com/jfcg/sixb
Let me know if you find one ;)
On Tue, Feb 19, 2019 at 10:44 AM Chris Burkert <[email protected]> wrote:
> Good Morning Serhat, here it is:
>
> # time ./prime2x
> prime2x xor: 0 collisions
>
> real 355m51.484s
> user 12490m36.231s
> sys 4079m42.192s
>
>>>> Am Mo., 18. Feb. 2019 um 08:47 Uhr schrieb Serhat Sevki Dincer
>>>> <[email protected]>:
>>>>> Great, can you also try xor version?
>>>>> I wonder if it will have any collisions.
>>>>>
>>>>> I made a tiny improvement to sorting here github.com/jfcg/sorty
>>>>>
>>>>> Thanks..
>>>>>
>>>>> 18 Şub 2019 Pzt 10:42 tarihinde Chris Burkert <[email protected]>
>>>>> şunu yazdı:
>>>>>> Hello Serhat,
>>>>>> this time it ran fine:
>>>>>>
>>>>>> # time ./prime2m
>>>>>> prime2m add: 0 collisions
>>>>>>
>>>>>> real 350m28.446s
>>>>>> user 12765m29.456s
>>>>>> sys 5997m49.762s
>>>>>>
>>>>>> cheers
>>>>>> Chris
>>>>>>
>>>>>> Am Mo., 18. Feb. 2019 um 08:11 Uhr schrieb Serhat Sevki Dincer
>>>>>> <[email protected]>:
>>>>>>> Thanks, how is the new code doing in terms of cpu / ram usage?
>>>>>>> Is it still running?
--
You received this message because you are subscribed to the Google Groups
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
package main
// Collision test for a simple hash with short utf8 text inputs
// Author: Serhat Şevki Dinçer, jfcgaussATgmail
import (
"fmt"
"github.com/jfcg/sorty"
)
func Txt2int(s string) uint64 {
x := uint64(len(s))
for i := len(s) - 1; i >= 0; i-- {
x *= 11400714819323198549
x ^= uint64(s[i])
}
return x
}
const N = 687194767360 // 274877906944
var hl = make([]uint64, N) // hash list: 5 TiB ram
var bf = [6]byte{30, 255, 127, 1, 1, 1} // input buffer
var sgch = make(chan bool, 1)
func hashRange(hl []uint64, bf [6]byte, signal bool) {
for i := len(hl) - 1; i >= 0; i-- {
hl[i] = Txt2int(string(bf[:]))
// next utf8-ish input
for k := 5; ; k-- {
bf[k] += 4
if bf[k] > 3 {
break
}
bf[k]++ // continue with carry
}
}
if signal {
sgch <- true
}
}
func main() {
const Q = N / 4 // 4 goroutines will fill hash list
for k := 0; k < 3; k++ {
go hashRange(hl[k*Q:(k+1)*Q], bf, true)
bf[5]++
}
hashRange(hl[3*Q:], bf, false) // main is the 4th goroutine
for k := 0; k < 3; k++ {
<-sgch // wait friends
}
sorty.ArU8 = hl
sorty.SortU8()
k := 0
for i := N - 1; i > 0; i-- {
if hl[i] == hl[i-1] {
k++
}
}
fmt.Println("prime2x xor:", k, "collisions") // xor
}
