2016-01-22.log

--- Log opened Fri Jan 22 00:00:11 2016
-!- JackH [~Jack@host-80-43-142-196.as13285.net] has joined #bitcoin-wizards00:05
-!- ThomasV [~ThomasV@unaffiliated/thomasv] has quit [Ping timeout: 272 seconds]00:05
-!- Linus_ [~LLinuss@garza.riseup.net] has joined #bitcoin-wizards00:09
-!- fn2187 [~fn2187@159.203.249.232] has joined #bitcoin-wizards00:09
-!- kelly [c0373628@gateway/web/freenode/ip.192.55.54.40] has joined #bitcoin-wizards00:13
kellydo most miners order the transactions in a block according to the time in which they received them, or by largest fee?00:15
kellyor do they select by largest fee, but then order temporally?00:15
Taektransactions are generally ordered in the block by fee-per-kb, with some variations due to cp4p and rbf00:16
Taek*I'm not a dev, info may be outdated or incorrect. Just remember some graphs I was staring at in HK00:16
kellythanks00:16
-!- DougieBot5000 [~DougieBot@unaffiliated/dougiebot5000] has quit [Quit: Leaving]00:17
kellyI knew that they were selected by fee00:17
Taekit should be noted that this is per-usual, there's no enforcement on how transactions are ordered00:17
kellyright00:17
-!- Guyver2 [~Guyver2@guyver2.xs4all.nl] has joined #bitcoin-wizards00:17
-!- Linus_ [~LLinuss@garza.riseup.net] has quit [Quit: Linus_]00:32
-!- p15 [~p15@70.91.145.64.client.static.strong-tk2.bringover.net] has quit [Ping timeout: 272 seconds]00:32
-!- LeMiner2 is now known as LeMiner00:32
-!- LeMiner [LeMiner@5ED1AFBF.cm-7-2c.dynamic.ziggo.nl] has quit [Changing host]00:32
-!- LeMiner [LeMiner@unaffiliated/leminer] has joined #bitcoin-wizards00:32
-!- dnaleor [~dnaleor@78-23-74-78.access.telenet.be] has joined #bitcoin-wizards00:33
phantomcircuitTaek, that is certainly how it works00:33
-!- Linus_ [~LLinuss@garza.riseup.net] has joined #bitcoin-wizards00:34
-!- p15 [~p15@12.91.145.64.client.static.strong-tk2.bringover.net] has joined #bitcoin-wizards00:39
-!- freekevin [freekevin@unaffiliated/freekevin] has quit [Ping timeout: 256 seconds]00:43
-!- zzyzx [~chatzilla@97-90-24-187.dhcp.mtpk.ca.charter.com] has quit [Ping timeout: 276 seconds]00:44
-!- CubicEarth [~cubiceart@c-67-168-82-178.hsd1.wa.comcast.net] has quit []00:45
-!- Myagui [Myagui@shell.xshellz.com] has quit [Ping timeout: 256 seconds]00:45
-!- freekevin [freekevin@unaffiliated/freekevin] has joined #bitcoin-wizards00:45
-!- Myagui [Myagui@shell.xshellz.com] has joined #bitcoin-wizards00:45
kellyI'd be interested to see what % of txns have the highest fee/kb as the first transaction in the block00:55
kellyif blockchain.info is to be trusted on the ordering (which is a big if) than bitfury isn't ordering like that00:58
kellyhttps://blockchain.info/block/000000000000000001473c57509de66a33771f9dc46974f948fd94eba7fcab8200:58
-!- memymo [~textual@c-24-4-69-49.hsd1.ca.comcast.net] has quit [Quit: My Mac has gone to sleep. ZZZzzz…]01:01
-!- andy-logbot [~bitcoin--@wpsoftware.net] has quit [Remote host closed the connection]01:05
-!- andy-logbot [~bitcoin--@wpsoftware.net] has joined #bitcoin-wizards01:05
* andy-logbot is logging01:05
-!- gavink [~g@184.75.223.211] has quit [Ping timeout: 250 seconds]01:08
-!- AaronVW [~ewout@x4db4880f.dyn.telefonica.de] has joined #bitcoin-wizards01:11
-!- AaronVW [~ewout@x4db4880f.dyn.telefonica.de] has quit [Remote host closed the connection]01:11
-!- ThomasV [~ThomasV@unaffiliated/thomasv] has joined #bitcoin-wizards01:13
-!- AaronvanW [~ewout@unaffiliated/aaronvanw] has joined #bitcoin-wizards01:15
-!- adam3us [~Adium@c-98-234-64-218.hsd1.ca.comcast.net] has quit [Quit: Leaving.]01:16
-!- adam3us [~Adium@c-98-234-64-218.hsd1.ca.comcast.net] has joined #bitcoin-wizards01:18
-!- adam3us [~Adium@c-98-234-64-218.hsd1.ca.comcast.net] has quit [Client Quit]01:21
-!- kelly [c0373628@gateway/web/freenode/ip.192.55.54.40] has quit [Ping timeout: 252 seconds]01:23
-!- freekevin [freekevin@unaffiliated/freekevin] has quit [Ping timeout: 240 seconds]01:32
-!- gmaxwell [greg@wikimedia/KatWalsh/x-0001] has joined #bitcoin-wizards01:32
gmaxwellhehe, trolls on reddit are sometimes entertaining:01:32
gmaxwell"Personally I like the idea of hashcash if, and only if, it's structured like a real currency as opposed to simply proof of work. In the real world you pay for resources used. In many cases this should also apply to P2P and other computer systems.01:32
gmaxwellOf course getting hashcash workable as a real currency is extremely difficult. I've thought of a scheme that would work (coins are signed by owner and can only be changed (signed to a different owner) by owner) except you need a decentralized "central" database of all the hashcash that's been minted. Unworkable. !@#$ spend-twice problem. :(" ... Peter Todd in 2001, on a mailing list with Hal and01:32
gmaxwellAdam Back01:33
-!- Myagui [Myagui@shell.xshellz.com] has quit [Ping timeout: 250 seconds]01:33
gmaxwellhttp://lists.ibiblio.org/pipermail/bluesky/2001-March.txt01:33
-!- Myagui [Myagui@shell.xshellz.com] has joined #bitcoin-wizards01:35
-!- freekevin [freekevin@unaffiliated/freekevin] has joined #bitcoin-wizards01:35
-!- Piper-Off is now known as Monthrect01:35
-!- veleiro [~veleiro@fsf/member/veleiro] has quit [Ping timeout: 245 seconds]01:38
-!- JackH [~Jack@host-80-43-142-196.as13285.net] has quit [Ping timeout: 260 seconds]01:43
-!- adam3us [~Adium@c-98-234-64-218.hsd1.ca.comcast.net] has joined #bitcoin-wizards01:45
-!- NewLiberty [~NewLibert@2602:304:cff8:1580:b8e2:1c9c:fe32:8ba2] has quit [Ping timeout: 250 seconds]01:45
-!- AndChat|435584 [~AndChat43@103.239.235.30] has joined #bitcoin-wizards01:46
nshgmaxwell, hi! :)01:48
fluffyponygmaxwell: did they conclude that petertodd == satoshi?01:53
-!- JackH [~Jack@host-80-43-140-111.as13285.net] has joined #bitcoin-wizards01:54
smooth"Hashcash at this scale makes me wince; all those wasted cycles..." --hal01:55
-!- veleiro [~veleiro@fsf/member/veleiro] has joined #bitcoin-wizards01:56
-!- gavink [~g@184.75.223.211] has joined #bitcoin-wizards01:56
-!- IAmNotDorian [~OrphanedG@unaffiliated/orphanedgland] has quit [Ping timeout: 276 seconds]02:01
frankenminthow do i build bitcoin from source??? just ./autogen.sh ... make install ?02:15
-!- ThomasV [~ThomasV@unaffiliated/thomasv] has quit [Ping timeout: 240 seconds]02:16
frankenmintstock options want to build .12 to try out a benchmarking script by altoidnerd02:16
frankenmintah okay so added ./configure02:17
-!- Guyver2 [~Guyver2@guyver2.xs4all.nl] has quit [Quit: :)]02:19
-!- AndChat|435584 [~AndChat43@103.239.235.30] has quit [Ping timeout: 250 seconds]02:24
-!- MrChrisJ [~MrChrisJ@cpc73828-dals21-2-0-cust929.20-2.cable.virginm.net] has joined #bitcoin-wizards02:36
-!- IAmNotDorian [~OrphanedG@97.84.216.139.dynamic.dsl.dv.iprimus.net.au] has joined #bitcoin-wizards02:36
-!- IAmNotDorian [~OrphanedG@97.84.216.139.dynamic.dsl.dv.iprimus.net.au] has quit [Changing host]02:36
-!- IAmNotDorian [~OrphanedG@unaffiliated/orphanedgland] has joined #bitcoin-wizards02:36
-!- frankenmint [~frankenmi@174-25-38-39.ptld.qwest.net] has quit [Remote host closed the connection]02:36
-!- frankenmint [~frankenmi@174-25-38-39.ptld.qwest.net] has joined #bitcoin-wizards02:55
-!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has joined #bitcoin-wizards03:00
-!- zmachine [~zmachine@pool-74-100-90-30.lsanca.fios.verizon.net] has quit [Ping timeout: 240 seconds]03:03
-!- zmachine [~zmachine@pool-74-100-90-30.lsanca.fios.verizon.net] has joined #bitcoin-wizards03:05
-!- ThomasV [~ThomasV@unaffiliated/thomasv] has joined #bitcoin-wizards03:09
-!- NewLiberty [~NewLibert@2602:304:cff8:1580:b8e2:1c9c:fe32:8ba2] has joined #bitcoin-wizards03:09
-!- Monthrect is now known as Piper-Off03:20
-!- dEBRUYNE [~dEBRUYNE@56-197-ftth.onsbrabantnet.nl] has joined #bitcoin-wizards03:27
-!- toffoo [~tof@unaffiliated/toffoo] has quit []03:40
-!- Linus_ [~LLinuss@garza.riseup.net] has quit [Ping timeout: 260 seconds]03:40
-!- nickeeem [~nickeem@cpe-104-32-148-17.socal.res.rr.com] has quit [Ping timeout: 256 seconds]03:40
-!- Yoghur114 [~Yoghurt11@131.224.198.111] has joined #bitcoin-wizards03:40
-!- laurentmt [~Thunderbi@213-245-86-6.rev.numericable.fr] has joined #bitcoin-wizards03:47
-!- moa [~kiwigb@opentransactions/dev/moa] has quit [Quit: Leaving.]03:51
-!- laurentmt [~Thunderbi@213-245-86-6.rev.numericable.fr] has quit [Ping timeout: 265 seconds]03:52
-!- dnaleor [~dnaleor@78-23-74-78.access.telenet.be] has quit [Ping timeout: 264 seconds]03:59
-!- tjader [~tjader@189.60.215.244] has quit [Ping timeout: 276 seconds]03:59
-!- alex___ [~alex@c-73-170-35-214.hsd1.ca.comcast.net] has joined #bitcoin-wizards04:01
-!- laurentmt [~Thunderbi@213-245-86-6.rev.numericable.fr] has joined #bitcoin-wizards04:04
-!- erasmospunk [~erasmospu@185.108.128.7] has joined #bitcoin-wizards04:04
-!- tjader [~tjader@189.60.215.244] has joined #bitcoin-wizards04:04
-!- alex___ [~alex@c-73-170-35-214.hsd1.ca.comcast.net] has quit [Ping timeout: 250 seconds]04:05
-!- eudoxia [~eudoxia@r167-56-138-69.dialup.adsl.anteldata.net.uy] has joined #bitcoin-wizards04:08
-!- face [~face@mail.hmel.org] has joined #bitcoin-wizards04:08
-!- eudoxia [~eudoxia@r167-56-138-69.dialup.adsl.anteldata.net.uy] has quit [Client Quit]04:10
-!- JackH [~Jack@host-80-43-140-111.as13285.net] has quit [Ping timeout: 264 seconds]04:10
-!- JackH [~Jack@host-80-43-140-156.as13285.net] has joined #bitcoin-wizards04:11
-!- dnaleor [~dnaleor@78-23-74-78.access.telenet.be] has joined #bitcoin-wizards04:12
-!- laurentmt [~Thunderbi@213-245-86-6.rev.numericable.fr] has quit [Ping timeout: 265 seconds]04:13
-!- ThomasV [~ThomasV@unaffiliated/thomasv] has quit [Quit: Quitte]04:16
-!- ThomasV [~ThomasV@unaffiliated/thomasv] has joined #bitcoin-wizards04:16
-!- NewLiberty [~NewLibert@2602:304:cff8:1580:b8e2:1c9c:fe32:8ba2] has quit [Ping timeout: 250 seconds]04:22
-!- laurentmt [~Thunderbi@213-245-86-6.rev.numericable.fr] has joined #bitcoin-wizards04:24
-!- alex___ [~alex@c-73-170-35-214.hsd1.ca.comcast.net] has joined #bitcoin-wizards04:32
-!- NewLiberty [~NewLibert@2602:304:cff8:1580:b8e2:1c9c:fe32:8ba2] has joined #bitcoin-wizards04:33
-!- laurentmt [~Thunderbi@213-245-86-6.rev.numericable.fr] has quit [Ping timeout: 276 seconds]04:34
-!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has quit [Quit: Leaving.]04:36
-!- alex___ [~alex@c-73-170-35-214.hsd1.ca.comcast.net] has quit [Ping timeout: 260 seconds]04:37
-!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has joined #bitcoin-wizards04:40
-!- laurentmt [~Thunderbi@213-245-86-6.rev.numericable.fr] has joined #bitcoin-wizards04:40
-!- dnaleor [~dnaleor@78-23-74-78.access.telenet.be] has quit [Remote host closed the connection]04:41
adlaifrankenmint: wrong channel?04:42
-!- laurentmt [~Thunderbi@213-245-86-6.rev.numericable.fr] has quit [Client Quit]04:43
-!- gavink [~g@184.75.223.211] has quit [Ping timeout: 240 seconds]04:43
-!- danielsocials [~quassel@45.32.248.113] has joined #bitcoin-wizards04:53
-!- NewLiberty [~NewLibert@2602:304:cff8:1580:b8e2:1c9c:fe32:8ba2] has quit [Ping timeout: 250 seconds]05:00
-!- priidu [~priidu@unaffiliated/priidu] has quit [Ping timeout: 240 seconds]05:02
-!- NewLiberty [~NewLibert@2602:304:cff8:1580:b8e2:1c9c:fe32:8ba2] has joined #bitcoin-wizards05:04
-!- contrapumpkin is now known as copumpkin05:08
-!- IAmNotDorian [~OrphanedG@unaffiliated/orphanedgland] has quit [Ping timeout: 276 seconds]05:24
-!- p15 [~p15@12.91.145.64.client.static.strong-tk2.bringover.net] has quit [Ping timeout: 240 seconds]05:27
-!- tjader [~tjader@189.60.215.244] has quit [Ping timeout: 276 seconds]05:30
-!- tjader [~tjader@189.60.215.244] has joined #bitcoin-wizards05:34
-!- WyzBTC [~Adium@72.10.98.195] has joined #bitcoin-wizards05:40
-!- Tiraspol [~Tiraspol3@unaffiliated/tiraspol] has quit [Remote host closed the connection]05:40
-!- Tiraspol [~Tiraspol3@unaffiliated/tiraspol] has joined #bitcoin-wizards05:41
-!- kabaum [~kalle@h-13-35.a163.priv.bahnhof.se] has quit [Quit: kabaum]05:41
-!- GGuyZ [~GGuyZ@216-15-125-203.c3-0.sbo-ubr1.sbo.ma.cable.rcn.com] has joined #bitcoin-wizards05:44
-!- GGuyZ [~GGuyZ@216-15-125-203.c3-0.sbo-ubr1.sbo.ma.cable.rcn.com] has quit [Client Quit]05:47
-!- NewLiberty [~NewLibert@2602:304:cff8:1580:b8e2:1c9c:fe32:8ba2] has quit [Ping timeout: 240 seconds]05:50
-!- Linus_ [~LLinuss@garza.riseup.net] has joined #bitcoin-wizards05:51
-!- stevenroose_ [~stevenroo@193.190.253.144] has joined #bitcoin-wizards05:51
-!- erasmospunk [~erasmospu@185.108.128.7] has quit [Remote host closed the connection]05:53
-!- markus-__ [~markus-k@designnet.work.de] has quit [Quit: My Mac has gone to sleep. ZZZzzz…]05:55
-!- erasmospunk [~erasmospu@185.108.128.7] has joined #bitcoin-wizards05:57
-!- alex_ [~alex@c-73-170-35-214.hsd1.ca.comcast.net] has joined #bitcoin-wizards05:58
-!- alex_ [~alex@c-73-170-35-214.hsd1.ca.comcast.net] has quit [Remote host closed the connection]05:58
-!- Yoghur114 [~Yoghurt11@131.224.198.111] has quit [Read error: Connection reset by peer]05:58
-!- danielsocials [~quassel@45.32.248.113] has quit [Remote host closed the connection]05:59
-!- alex_ [~alex@c-73-170-35-214.hsd1.ca.comcast.net] has joined #bitcoin-wizards05:59
-!- erasmosp_ [~erasmospu@185.108.128.7] has joined #bitcoin-wizards05:59
-!- danielsocials [~quassel@45.32.248.113] has joined #bitcoin-wizards06:00
-!- markus-k_ [~markus-k@p5499544C.dip0.t-ipconnect.de] has joined #bitcoin-wizards06:00
-!- erasmospunk [~erasmospu@185.108.128.7] has quit [Ping timeout: 245 seconds]06:02
-!- zzyzx [~chatzilla@97-90-24-187.dhcp.mtpk.ca.charter.com] has joined #bitcoin-wizards06:02
-!- bit2017 [~linker@115.79.55.177] has quit [Ping timeout: 240 seconds]06:02
-!- Tiraspol [~Tiraspol3@unaffiliated/tiraspol] has quit [Remote host closed the connection]06:02
-!- Tiraspol [~Tiraspol3@unaffiliated/tiraspol] has joined #bitcoin-wizards06:02
-!- erasmosp_ [~erasmospu@185.108.128.7] has quit [Ping timeout: 264 seconds]06:05
-!- sparetire [~sparetire@unaffiliated/sparetire] has joined #bitcoin-wizards06:05
-!- danielsocials [~quassel@45.32.248.113] has quit [Ping timeout: 276 seconds]06:06
-!- Iriez [xbins@distribution.xbins.org] has quit [Ping timeout: 244 seconds]06:11
-!- erasmospunk [~erasmospu@185.108.128.7] has joined #bitcoin-wizards06:12
-!- erasmospunk [~erasmospu@185.108.128.7] has quit [Remote host closed the connection]06:13
-!- erasmospunk [~erasmospu@185.108.128.7] has joined #bitcoin-wizards06:13
-!- zooko [~user@2601:281:8001:26aa:e5a2:d20a:75ce:a1d9] has quit [Ping timeout: 240 seconds]06:14
-!- erasmospunk [~erasmospu@185.108.128.7] has quit [Remote host closed the connection]06:15
-!- erasmospunk [~erasmospu@151.41.84.55] has joined #bitcoin-wizards06:16
-!- danielsocials [~quassel@45.32.248.113] has joined #bitcoin-wizards06:19
-!- Tiraspol [~Tiraspol3@unaffiliated/tiraspol] has quit [Remote host closed the connection]06:19
-!- Tiraspol [~Tiraspol3@unaffiliated/tiraspol] has joined #bitcoin-wizards06:20
-!- IAmNotDorian [~OrphanedG@97.84.216.139.dynamic.dsl.dv.iprimus.net.au] has joined #bitcoin-wizards06:20
-!- IAmNotDorian [~OrphanedG@97.84.216.139.dynamic.dsl.dv.iprimus.net.au] has quit [Changing host]06:20
-!- IAmNotDorian [~OrphanedG@unaffiliated/orphanedgland] has joined #bitcoin-wizards06:20
-!- MrChrisJ [~MrChrisJ@cpc73828-dals21-2-0-cust929.20-2.cable.virginm.net] has quit [Quit: MrChrisJ]06:21
-!- erasmospunk [~erasmospu@151.41.84.55] has quit [Ping timeout: 264 seconds]06:21
-!- erasmosp_ [~erasmospu@185.108.128.7] has joined #bitcoin-wizards06:21
-!- erasmosp_ [~erasmospu@185.108.128.7] has quit [Remote host closed the connection]06:22
-!- erasmospunk [~erasmospu@185.108.128.11] has joined #bitcoin-wizards06:24
-!- danielsocials [~quassel@45.32.248.113] has quit [Remote host closed the connection]06:26
-!- MrChrisJ [~MrChrisJ@cpc73828-dals21-2-0-cust929.20-2.cable.virginm.net] has joined #bitcoin-wizards06:31
-!- ThomasV [~ThomasV@unaffiliated/thomasv] has quit [Ping timeout: 250 seconds]06:32
-!- dnaleor [~dnaleor@78-23-74-78.access.telenet.be] has joined #bitcoin-wizards06:33
kanzurescala-based lightning network implementation thingy https://github.com/ACINQ/eclair06:34
-!- Iriez [xbins@distribution.xbins.org] has joined #bitcoin-wizards06:38
frankenmintadlai: pretty much I got it figured out I think06:41
-!- markus-k_ [~markus-k@p5499544C.dip0.t-ipconnect.de] has quit [Quit: My Mac has gone to sleep. ZZZzzz…]06:43
-!- seg [~seg@fsf/member/seg] has quit [Quit: kuwabara kuwabara]06:44
-!- seg [~seg@fsf/member/seg] has joined #bitcoin-wizards06:46
-!- sergiohlb [sergiohlb@unaffiliated/sergiohlb] has joined #bitcoin-wizards06:47
-!- Tiraspol [~Tiraspol3@unaffiliated/tiraspol] has quit [Remote host closed the connection]06:51
-!- Tiraspol [~Tiraspol3@c-98-212-187-224.hsd1.il.comcast.net] has joined #bitcoin-wizards06:52
-!- Tiraspol [~Tiraspol3@c-98-212-187-224.hsd1.il.comcast.net] has quit [Changing host]06:52
-!- Tiraspol [~Tiraspol3@unaffiliated/tiraspol] has joined #bitcoin-wizards06:52
frankenmintthank you kanzure, im reading the pdf on the bottom of the implementation page seems like a pt 2 to the orig. proposal06:54
frankenmintseems like the jist is a soft fork version of lightning now???06:54
-!- IAmNotDorian [~OrphanedG@unaffiliated/orphanedgland] has quit [Ping timeout: 256 seconds]06:55
-!- danielsocials [~quassel@45.32.248.113] has joined #bitcoin-wizards06:57
-!- tjader [~tjader@189.60.215.244] has quit [Ping timeout: 276 seconds]07:00
-!- paveljanik [~paveljani@79-98-72-216.sys-data.com] has joined #bitcoin-wizards07:01
-!- paveljanik [~paveljani@79-98-72-216.sys-data.com] has quit [Changing host]07:01
-!- paveljanik [~paveljani@unaffiliated/paveljanik] has joined #bitcoin-wizards07:01
-!- danielsocials [~quassel@45.32.248.113] has quit [Ping timeout: 250 seconds]07:02
-!- Tiraspol [~Tiraspol3@unaffiliated/tiraspol] has quit [Remote host closed the connection]07:03
-!- Tiraspol [~Tiraspol3@c-98-212-187-224.hsd1.il.comcast.net] has joined #bitcoin-wizards07:03
-!- Tiraspol [~Tiraspol3@c-98-212-187-224.hsd1.il.comcast.net] has quit [Changing host]07:03
-!- Tiraspol [~Tiraspol3@unaffiliated/tiraspol] has joined #bitcoin-wizards07:03
-!- danielsocials [~quassel@45.32.248.113] has joined #bitcoin-wizards07:03
-!- tjader [~tjader@189.60.215.244] has joined #bitcoin-wizards07:04
nshtromp_, how much speedup would you get for your GO solver if you rewrote it as a quantum algorithm? just grover quadratic, or better?07:05
nsh*Go07:05
-!- AndChat|435584 [~AndChat43@103.239.235.30] has joined #bitcoin-wizards07:05
tromp_what Go solver?07:05
nshdid you do this? http://tromp.github.io/go/legal19.html07:06
tromp_that's a counter, not a solver:)07:06
nshoh, sorry07:06
tromp_there's no search involved there, so i don't see any quantum speedup07:06
nshi just wondered if there are better algorithms for solving than brute-force07:07
nshand where they sit in the complexity zoo07:07
tromp_by solving, you mean finding the best result of a two player game?07:08
tromp_those are generally PSPACE complete07:08
nshi guess i mean an algorithm that returns the perfect next play for a given board position07:09
nshthere will be some minimal representation of the perfect strategy, by Kolmogorov07:09
nsh(for a given board size)07:10
tromp_yes, that will just be a minimax solver07:10
-!- IAmNotDorian [~OrphanedG@97.84.216.139.dynamic.dsl.dv.iprimus.net.au] has joined #bitcoin-wizards07:11
-!- IAmNotDorian [~OrphanedG@97.84.216.139.dynamic.dsl.dv.iprimus.net.au] has quit [Changing host]07:11
-!- IAmNotDorian [~OrphanedG@unaffiliated/orphanedgland] has joined #bitcoin-wizards07:11
tromp_such as this one http://tromp.github.io/java/go/twoxtwo.html07:11
nshso i guess my quesiton resolves to whether or not minimax exhibits 'structure' that allows for quantum speedup07:12
-!- NewLiberty [~NewLibert@2602:304:cff8:1580:b8e2:1c9c:fe32:8ba2] has joined #bitcoin-wizards07:13
nsh' Performing any form of minimax search on a quantum computer in better than exponential time is ridiculously unlikely, and one would expect at most a modest (polynomial) speedup compared to now. This much is already proved by the existing literature.' -- http://senseis.xmp.net/?QuantumComputing07:13
nshheh07:14
nsh'However, the expression "solving go", as if we were doing sudoku, is wrong. It's like saying you could solve art, or solve mathematics (googleFor:Göedel). Simply, there are things you can not compute. Anyone who's played enough Go knows that this isn't a game a about mere calculations, there is a lot of right brain hemisphere activity going on as well. There are a lot of factors involved in a Go m07:14
nshatch, and understanding another person's intentions is no easy task for machines. It's a human capacity known as "empathy"; I just don't think machines might get right-hemisphere-type artificial intelligence someday, creative tasks and abstract reasoning, aesthetics perception, intuition, imaginative process.. result => does not compute, I think. '07:14
nshthat's a very strong position contra computational church turing07:15
tromp_i think that's enough way off topic for now:)07:15
nshi find it increasingly hard to think of any kind of physics as noncomputational. so the idea of a brain doing something other than calculations in some abstract sense seems pretty devoid of meaning07:15
* nsh nods07:15
nshmy bad07:15
kanzurei think i solved 100 arts07:15
instagibbs#bitcoin-wizards-offtopic07:15
-!- memymo [~textual@c-24-4-69-49.hsd1.ca.comcast.net] has joined #bitcoin-wizards07:16
-!- IAmNotDorian [~OrphanedG@unaffiliated/orphanedgland] has quit [Ping timeout: 250 seconds]07:18
-!- danielsocials [~quassel@45.32.248.113] has quit [Remote host closed the connection]07:19
-!- NewLiberty [~NewLibert@2602:304:cff8:1580:b8e2:1c9c:fe32:8ba2] has quit [Ping timeout: 250 seconds]07:19
-!- erasmosp_ [~erasmospu@151.41.84.55] has joined #bitcoin-wizards07:20
-!- Yoghur114 [~Yoghurt11@131.224.198.111] has joined #bitcoin-wizards07:20
-!- zookolaptop [~user@50.246.213.170] has joined #bitcoin-wizards07:21
-!- bityogi [~textual@208-104-143-200.brvd.dsl.dyn.comporium.net] has joined #bitcoin-wizards07:22
-!- erasmospunk [~erasmospu@185.108.128.11] has quit [Ping timeout: 272 seconds]07:24
-!- Yoghur114 [~Yoghurt11@131.224.198.111] has quit []07:27
-!- zookolaptop [~user@50.246.213.170] has quit [Ping timeout: 256 seconds]07:27
-!- bit2017 [~linker@171.250.100.197] has joined #bitcoin-wizards07:29
-!- GGuyZ [~GGuyZ@216-15-125-203.c3-0.sbo-ubr1.sbo.ma.cable.rcn.com] has joined #bitcoin-wizards07:30
-!- Tiraspol [~Tiraspol3@unaffiliated/tiraspol] has quit []07:30
-!- Giszmo [~leo@pc-139-55-215-201.cm.vtr.net] has joined #bitcoin-wizards07:32
-!- NewLiberty [~NewLibert@2602:304:cff8:1580:b8e2:1c9c:fe32:8ba2] has joined #bitcoin-wizards07:41
-!- IAmNotDorian [~OrphanedG@97.84.216.139.dynamic.dsl.dv.iprimus.net.au] has joined #bitcoin-wizards07:44
-!- IAmNotDorian [~OrphanedG@97.84.216.139.dynamic.dsl.dv.iprimus.net.au] has quit [Changing host]07:44
-!- IAmNotDorian [~OrphanedG@unaffiliated/orphanedgland] has joined #bitcoin-wizards07:44
-!- DougieBot5000 [~DougieBot@unaffiliated/dougiebot5000] has joined #bitcoin-wizards07:49
-!- erasmosp_ [~erasmospu@151.41.84.55] has quit [Remote host closed the connection]07:52
-!- erasmospunk [~erasmospu@151.41.84.55] has joined #bitcoin-wizards07:57
-!- AndChat|435584 [~AndChat43@103.239.235.30] has quit [Remote host closed the connection]08:04
-!- skyraider_ [uid41097@gateway/web/irccloud.com/x-hzzzjzviabokeiok] has joined #bitcoin-wizards08:12
-!- GGuyZ [~GGuyZ@216-15-125-203.c3-0.sbo-ubr1.sbo.ma.cable.rcn.com] has quit [Quit: GGuyZ]08:23
-!- voxelot [~voxelot@remote.digitalmoneycorp.com] has joined #bitcoin-wizards08:24
-!- alex_ [~alex@c-73-170-35-214.hsd1.ca.comcast.net] has quit [Remote host closed the connection]08:24
-!- GGuyZ [~GGuyZ@216-15-125-203.c3-0.sbo-ubr1.sbo.ma.cable.rcn.com] has joined #bitcoin-wizards08:24
-!- alex_ [~alex@c-73-170-35-214.hsd1.ca.comcast.net] has joined #bitcoin-wizards08:25
-!- c0rw|zZz is now known as c0rw1n08:29
-!- tjader [~tjader@189.60.215.244] has quit [Ping timeout: 276 seconds]08:30
-!- tjader [~tjader@189.60.215.244] has joined #bitcoin-wizards08:34
-!- IAmNotDorian [~OrphanedG@unaffiliated/orphanedgland] has quit [Ping timeout: 250 seconds]08:38
-!- ThomasV [~ThomasV@unaffiliated/thomasv] has joined #bitcoin-wizards08:41
-!- arowser [~quassel@106.120.101.38] has quit [Quit: No Ping reply in 180 seconds.]08:45
-!- arowser [~quassel@106.120.101.38] has joined #bitcoin-wizards08:45
-!- Dizzle [~Dizzle@104-6-36-162.lightspeed.austtx.sbcglobal.net] has joined #bitcoin-wizards08:46
-!- murch [~murch@p4FE394A2.dip0.t-ipconnect.de] has joined #bitcoin-wizards08:52
-!- sergiohlb [sergiohlb@unaffiliated/sergiohlb] has quit [Ping timeout: 240 seconds]09:00
-!- alex_ [~alex@c-73-170-35-214.hsd1.ca.comcast.net] has quit [Remote host closed the connection]09:06
-!- alex_ [~alex@c-73-170-35-214.hsd1.ca.comcast.net] has joined #bitcoin-wizards09:07
-!- alex_ [~alex@c-73-170-35-214.hsd1.ca.comcast.net] has quit [Read error: Connection reset by peer]09:09
-!- alex_ [~alex@c-73-170-35-214.hsd1.ca.comcast.net] has joined #bitcoin-wizards09:09
-!- alex_ [~alex@c-73-170-35-214.hsd1.ca.comcast.net] has quit [Ping timeout: 276 seconds]09:14
-!- phiche [~Adium@193.89.191.209] has quit [Ping timeout: 250 seconds]09:16
-!- danielsocials [~quassel@45.32.248.113] has joined #bitcoin-wizards09:17
-!- danielsocials [~quassel@45.32.248.113] has quit [Remote host closed the connection]09:19
bsm117532Can anyone provide any references on distributed, deterministic order matching?  i.e. imagine that instead of a block containing UTXO's, it contained an order book with bids and asks, which get matched deterministically. I know a few projects do this, effectively.09:19
-!- adam3us [~Adium@c-98-234-64-218.hsd1.ca.comcast.net] has quit [Quit: Leaving.]09:20
-!- phiche [~Adium@37.250.46.20.bredband.tre.se] has joined #bitcoin-wizards09:21
-!- nivah [~linker@27.75.174.138] has joined #bitcoin-wizards09:21
-!- N0S4A2 [~weechat@216-243-38-141.users.condointernet.net] has quit [Quit: WeeChat 1.3]09:22
-!- bit2017 [~linker@171.250.100.197] has quit [Ping timeout: 250 seconds]09:22
nshwhich projects?09:23
nshi mean, there are obvious trivial impossibility results unless you loosen the notion of strict sequential matching because a distributed system does not have a common proper time09:23
-!- N0S4A2 [~weechat@216-243-38-141.users.condointernet.net] has joined #bitcoin-wizards09:24
nshand loosening that without it being open to gaming or other problems seems tricky09:24
-!- phiche1 [~Adium@185.97.214.102] has joined #bitcoin-wizards09:24
-!- arowser [~quassel@106.120.101.38] has quit [Quit: No Ping reply in 180 seconds.]09:25
-!- phiche [~Adium@37.250.46.20.bredband.tre.se] has quit [Ping timeout: 265 seconds]09:26
-!- frankenmint [~frankenmi@174-25-38-39.ptld.qwest.net] has quit [Remote host closed the connection]09:26
-!- arowser [~quassel@106.120.101.38] has joined #bitcoin-wizards09:26
bsm117532nsh: that's exactly what I was hoping to find literature on.  CounterParty, NXT, etc claim to do it.09:27
nshshout if you find any!09:28
bsm117532I was thinking naively of publishing all orders in a "block" (bids and asks would overlap) and having deterministic resolution rules.  But I'm sure it can be gamed...09:28
nshyou can make it so the expected utility of gaming is below some cost threshold09:28
nshthat's the generic solution i suspect09:28
bsm117532obviously, a time based first-in-first-out isn't possible in a distributed system...09:29
nshbut when a single trade can be massively valuable, that's hard09:29
nshso might result in having to set a maximum order-differential value delta09:29
nshif that makes sense?09:29
nshwhich will mean some bid/asks will have to be broken up09:29
bsm117532Partial fills are a requiremenet.09:29
nshor else another way to prevent a reordering changing value too much09:29
nshwhat's a partial fill?09:29
bsm117532Two people place orders for 100 units against an existing sell of 100 units, each would get 50.09:30
bsm117532(only fair way to do it if you don't have time ordering)09:30
nshah i see09:31
nshyeah, in that case if you define the degree of order overlap and apply partial fill, then it's pretty much optimally fair09:31
bsm117532The gaming I think would come down to non-random oracle of your hash function.  Taking all the orders to be matched you can make a PRNG to decide (e.g. rounding of partial fills).09:31
nshbut because that depends on latency which is hard to predict, you probably end up having to fine-tune the err09:32
nshhmm09:32
bsm117532Why would latency matter?09:32
bsm117532Just imagine a "tick" sending out the order book once per time interval, just like blocks.09:32
nshbecause 'now' depends on the now of elsewhere getting to you09:32
-!- NewLiberty [~NewLibert@2602:304:cff8:1580:b8e2:1c9c:fe32:8ba2] has quit [Ping timeout: 260 seconds]09:32
nshand that depends on network stuff that's out of our hands09:32
bsm117532Imagine the tick is long enough that all participants have a chance to see the order book and react (so, more than a second, roughly009:32
* nsh nods09:33
-!- alex_ [~alex@96.82.80.25] has joined #bitcoin-wizards09:33
bsm117532I think this is what CounterParty does...09:33
nshso i characterised bitcoin this way once, in terms of conflict-free replicated data types09:33
nshin which you have operation-based and state-based, but bitcoin ends up being a hybrid of these due to blocktime 'tick' as you say09:34
nsh--09:34
nshOperation-based CRDTs are called commutative replicated data types, or CmRDTs. CmRDT replicas propagate state by broadcasting the state update operation itself, which must be commutative. For example, a CmRDT of a single integer might broadcast the operations (+10) or (-20). Replicas receive the updates and apply them locally. The operations are commutative, so can be received and applied in any ord09:34
nsher; however, they are not idempotent, and additional network protocol guarantees are required to ensure unique delivery.09:34
nsh-- block propagatoins09:34
nshState-based CRDTs are called convergent replicated data types, or CvRDTs. In contrast to CmRDTs, CvRDTs send their full local state to other replicas. CvRDTs have the following local interface:09:34
nsh    query - reads the state of the replica, with no side effects09:34
nsh    update - writes to the replica state in accordance with certain restrictions09:34
nsh    merge - merges local state with the state of some remote replica09:34
nsh-- transaction propagation09:34
bsm117532egads you should read some of the things I've written privately. It's like you read my mind...09:35
nshhehe :D09:35
-!- alex_ [~alex@96.82.80.25] has quit [Remote host closed the connection]09:35
-!- alex_ [~alex@96.82.80.25] has joined #bitcoin-wizards09:35
bsm117532One side thought I've been having is the notion of commutative updates, conflict-resolvable, and conflicting updates.09:35
bsm117532e.g. multiple sequential spends from a single UTXO could in principle be merged, instead of being a double spend in bitcoin.09:36
nshright09:37
-!- Piper-Off is now known as Monthrect09:39
-!- Erik_dc [~erik@d54c620ed.access.telenet.be] has joined #bitcoin-wizards09:40
-!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has quit [Quit: Leaving.]09:44
-!- darmou [~darmou@c-73-241-146-77.hsd1.ca.comcast.net] has joined #bitcoin-wizards09:48
-!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has joined #bitcoin-wizards09:48
-!- frankenmint [~frankenmi@174-25-38-39.ptld.qwest.net] has joined #bitcoin-wizards09:55
-!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has quit [Quit: Leaving.]09:56
-!- tjader [~tjader@189.60.215.244] has quit [Ping timeout: 276 seconds]10:00
-!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has joined #bitcoin-wizards10:01
-!- tjader [~tjader@189.60.215.244] has joined #bitcoin-wizards10:04
-!- nonaTure [~happy@94.155.72.86] has quit [Ping timeout: 264 seconds]10:12
-!- phiche1 [~Adium@185.97.214.102] has quit [Ping timeout: 265 seconds]10:13
-!- dnaleor [~dnaleor@78-23-74-78.access.telenet.be] has quit [Quit: Leaving]10:15
-!- phiche [~Adium@37.250.46.20.bredband.tre.se] has joined #bitcoin-wizards10:17
-!- danielsocials [~quassel@45.32.248.113] has joined #bitcoin-wizards10:18
-!- danielsocials [~quassel@45.32.248.113] has quit [Remote host closed the connection]10:22
-!- nonaTure [~happy@179.43.176.98] has joined #bitcoin-wizards10:28
-!- Emcy [~MC@unaffiliated/mc1984] has quit [Ping timeout: 240 seconds]10:28
-!- frankenmint [~frankenmi@174-25-38-39.ptld.qwest.net] has quit [Remote host closed the connection]10:32
-!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has quit [Quit: Leaving.]10:33
-!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has joined #bitcoin-wizards10:33
-!- priidu [~priidu@unaffiliated/priidu] has joined #bitcoin-wizards10:37
-!- jtimon [~quassel@126.31.134.37.dynamic.jazztel.es] has joined #bitcoin-wizards10:38
-!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has quit [Quit: Leaving.]10:40
-!- frankenmint [~frankenmi@174-25-38-39.ptld.qwest.net] has joined #bitcoin-wizards10:48
-!- blackwraith [~priidu@unaffiliated/priidu] has joined #bitcoin-wizards10:48
-!- priidu [~priidu@unaffiliated/priidu] has quit [Ping timeout: 276 seconds]10:50
-!- sausage_factory [~priidu@unaffiliated/priidu] has joined #bitcoin-wizards10:51
-!- mihar [~mihar@4.16.87.162] has joined #bitcoin-wizards10:52
-!- blackwraith [~priidu@unaffiliated/priidu] has quit [Ping timeout: 272 seconds]10:53
-!- ThomasV [~ThomasV@unaffiliated/thomasv] has quit [Ping timeout: 240 seconds]10:54
-!- ThomasV [~ThomasV@unaffiliated/thomasv] has joined #bitcoin-wizards10:58
-!- GGuyZ [~GGuyZ@216-15-125-203.c3-0.sbo-ubr1.sbo.ma.cable.rcn.com] has quit [Read error: No route to host]11:04
-!- MrChrisJ [~MrChrisJ@cpc73828-dals21-2-0-cust929.20-2.cable.virginm.net] has quit [Quit: MrChrisJ]11:08
-!- ThomasV [~ThomasV@unaffiliated/thomasv] has quit [Ping timeout: 245 seconds]11:08
-!- adam3us [~Adium@172.56.39.208] has joined #bitcoin-wizards11:08
-!- memymo [~textual@c-24-4-69-49.hsd1.ca.comcast.net] has quit [Quit: My Mac has gone to sleep. ZZZzzz…]11:13
-!- brg444 [18257df2@gateway/web/freenode/ip.24.37.125.242] has joined #bitcoin-wizards11:21
-!- tjader [~tjader@189.60.215.244] has quit [Ping timeout: 276 seconds]11:28
-!- darmou [~darmou@c-73-241-146-77.hsd1.ca.comcast.net] has quit [Quit: My Mac has gone to sleep. ZZZzzz…]11:32
-!- tjader [~tjader@189.60.215.244] has joined #bitcoin-wizards11:35
-!- darmou [~darmou@c-73-241-146-77.hsd1.ca.comcast.net] has joined #bitcoin-wizards11:36
-!- darmou [~darmou@c-73-241-146-77.hsd1.ca.comcast.net] has quit [Client Quit]11:36
-!- dnaleor [~dnaleor@78-23-74-78.access.telenet.be] has joined #bitcoin-wizards11:38
-!- Jeremy_Rand_2 [~user@ip68-97-38-24.ok.ok.cox.net] has quit [Ping timeout: 256 seconds]11:43
-!- zookolaptop [~user@c-24-9-79-61.hsd1.co.comcast.net] has joined #bitcoin-wizards11:45
-!- jposner [~jposner@172.98.67.68] has quit [Remote host closed the connection]11:46
-!- zookolaptop [~user@c-24-9-79-61.hsd1.co.comcast.net] has quit [Ping timeout: 240 seconds]11:53
-!- jposner [~jposner@172.98.67.68] has joined #bitcoin-wizards11:54
-!- gocrazy [~gocrazey@216.240.144.97] has quit [Ping timeout: 256 seconds]12:02
-!- gocrazy [~gocrazey@216.240.144.97] has joined #bitcoin-wizards12:02
-!- stevenroose_ [~stevenroo@193.190.253.144] has quit [Ping timeout: 240 seconds]12:03
-!- memymo [~textual@184-23-239-227.dedicated.static.sonic.net] has joined #bitcoin-wizards12:04
-!- raedah [~raedah@172.56.39.61] has joined #bitcoin-wizards12:07
-!- erasmospunk [~erasmospu@151.41.84.55] has quit [Remote host closed the connection]12:08
-!- jposner [~jposner@172.98.67.68] has quit [Remote host closed the connection]12:09
-!- Dizzle [~Dizzle@104-6-36-162.lightspeed.austtx.sbcglobal.net] has quit [Quit: Leaving...]12:10
-!- erasmospunk [~erasmospu@151.41.84.55] has joined #bitcoin-wizards12:13
-!- rusty [~rusty@pdpc/supporter/bronze/rusty] has joined #bitcoin-wizards12:17
-!- jposner [~jposner@172.98.67.41] has joined #bitcoin-wizards12:17
-!- c0rw1n [~c0rw1n@91.178.230.245] has quit []12:19
-!- c0rw1n [~c0rw1n@91.178.230.245] has joined #bitcoin-wizards12:19
-!- darmou [~darmou@c-73-241-146-77.hsd1.ca.comcast.net] has joined #bitcoin-wizards12:21
-!- danielsocials [~quassel@45.32.248.113] has joined #bitcoin-wizards12:22
-!- adam3us [~Adium@172.56.39.208] has quit [Quit: Leaving.]12:22
-!- polyclef [~polyclef@184-23-239-227.dedicated.static.sonic.net] has joined #bitcoin-wizards12:26
-!- danielsocials [~quassel@45.32.248.113] has quit [Ping timeout: 256 seconds]12:27
-!- everyBloc [~everybloc@c-73-158-140-36.hsd1.ca.comcast.net] has quit []12:29
-!- darmou [~darmou@c-73-241-146-77.hsd1.ca.comcast.net] has quit [Quit: My Mac has gone to sleep. ZZZzzz…]12:29
-!- darmou [~darmou@c-73-241-146-77.hsd1.ca.comcast.net] has joined #bitcoin-wizards12:30
-!- dnaleor_ [~dnaleor@78-23-74-78.access.telenet.be] has joined #bitcoin-wizards12:31
-!- dnaleor_ [~dnaleor@78-23-74-78.access.telenet.be] has quit [Client Quit]12:32
-!- alex_ [~alex@96.82.80.25] has quit []12:40
-!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has joined #bitcoin-wizards12:41
-!- adam3us [~Adium@172.56.39.208] has joined #bitcoin-wizards12:41
-!- Jeremy_Rand_2 [~user@172.56.6.48] has joined #bitcoin-wizards12:41
-!- davec [~davec@cpe-24-243-251-52.hot.res.rr.com] has quit [Read error: Connection reset by peer]12:45
-!- davec [~davec@cpe-24-243-251-52.hot.res.rr.com] has joined #bitcoin-wizards12:46
-!- OxADADA [~OxADADA@alumni-linux.ccs.neu.edu] has quit [Quit: leaving]12:46
-!- OxADADA [~OxADADA@alumni-linux.ccs.neu.edu] has joined #bitcoin-wizards12:47
-!- riplin [9f998840@gateway/web/freenode/ip.159.153.136.64] has joined #bitcoin-wizards12:48
-!- Logicwax [~Logicwax@c-76-126-174-152.hsd1.ca.comcast.net] has quit [Remote host closed the connection]12:52
-!- riplin [9f998840@gateway/web/freenode/ip.159.153.136.64] has quit [Quit: Page closed]12:54
-!- Logicwax [~Logicwax@c-76-126-174-152.hsd1.ca.comcast.net] has joined #bitcoin-wizards12:55
-!- T23WS [~textual@45.56.159.8] has joined #bitcoin-wizards12:57
-!- tjader [~tjader@189.60.215.244] has quit [Ping timeout: 276 seconds]13:00
-!- voxelot [~voxelot@remote.digitalmoneycorp.com] has quit [Ping timeout: 240 seconds]13:01
-!- Jeremy_Rand_2 [~user@172.56.6.48] has quit [Ping timeout: 264 seconds]13:04
-!- tjader [~tjader@189.60.215.244] has joined #bitcoin-wizards13:05
-!- dcousens [~anon@c110-22-219-15.sunsh4.vic.optusnet.com.au] has quit [Ping timeout: 276 seconds]13:08
-!- melvster [~melvster@ip-86-49-18-198.net.upcbroadband.cz] has quit [Ping timeout: 250 seconds]13:08
-!- Linus_ [~LLinuss@garza.riseup.net] has quit [Ping timeout: 240 seconds]13:10
-!- Jeremy_Rand_2 [~user@172.58.104.229] has joined #bitcoin-wizards13:12
-!- Guyver2 [~Guyver2@guyver2.xs4all.nl] has joined #bitcoin-wizards13:12
-!- melvster [~melvster@ip-86-49-18-198.net.upcbroadband.cz] has joined #bitcoin-wizards13:22
-!- zzyzx [~chatzilla@97-90-24-187.dhcp.mtpk.ca.charter.com] has quit [Quit: ChatZilla 0.9.92 [SeaMonkey 2.39/20151103191810]]13:27
-!- erasmospunk [~erasmospu@151.41.84.55] has quit [Remote host closed the connection]13:32
-!- zookolaptop [~user@72.42.70.227] has joined #bitcoin-wizards13:36
-!- zookolaptop is now known as zooko13:37
-!- T23WS [~textual@45.56.159.8] has quit [Ping timeout: 240 seconds]13:39
-!- voxelot [~voxelot@remote.digitalmoneycorp.com] has joined #bitcoin-wizards13:40
-!- MrChrisJ [~MrChrisJ@host86-128-121-45.range86-128.btcentralplus.com] has joined #bitcoin-wizards13:42
-!- Jeremy_Rand_2 [~user@172.58.104.229] has quit [Ping timeout: 250 seconds]13:44
-!- adam3us1 [~Adium@184-23-239-227.dedicated.static.sonic.net] has joined #bitcoin-wizards13:44
-!- adam3us1 [~Adium@184-23-239-227.dedicated.static.sonic.net] has quit [Client Quit]13:44
-!- adam3us1 [~Adium@184-23-239-227.dedicated.static.sonic.net] has joined #bitcoin-wizards13:44
-!- adam3us1 [~Adium@184-23-239-227.dedicated.static.sonic.net] has quit [Client Quit]13:44
-!- adam3us1 [~Adium@184-23-239-227.dedicated.static.sonic.net] has joined #bitcoin-wizards13:45
-!- adam3us1 [~Adium@184-23-239-227.dedicated.static.sonic.net] has quit [Client Quit]13:45
-!- adam3us1 [~Adium@184-23-239-227.dedicated.static.sonic.net] has joined #bitcoin-wizards13:45
-!- WyzBTC [~Adium@72.10.98.195] has quit [Ping timeout: 272 seconds]13:46
-!- adam3us [~Adium@172.56.39.208] has quit [Ping timeout: 265 seconds]13:47
-!- e_low is now known as prosody13:48
-!- gavink [~g@184.75.223.211] has joined #bitcoin-wizards13:57
-!- melvster [~melvster@ip-86-49-18-198.net.upcbroadband.cz] has quit [Read error: Connection reset by peer]13:57
-!- rusty [~rusty@pdpc/supporter/bronze/rusty] has quit [Ping timeout: 240 seconds]13:58
-!- melvster [~melvster@ip-86-49-18-198.net.upcbroadband.cz] has joined #bitcoin-wizards13:58
-!- dcousens [~anon@1.136.96.213] has joined #bitcoin-wizards14:03
-!- MoALTz [~no@78-11-180-214.static.ip.netia.com.pl] has quit [Quit: Leaving]14:07
-!- zzyzx [~chatzilla@97-90-24-187.dhcp.mtpk.ca.charter.com] has joined #bitcoin-wizards14:09
-!- mkarrer_ [~mkarrer@211.Red-2-138-29.dynamicIP.rima-tde.net] has joined #bitcoin-wizards14:12
-!- adam3us1 [~Adium@184-23-239-227.dedicated.static.sonic.net] has quit [Quit: Leaving.]14:17
-!- darmou [~darmou@c-73-241-146-77.hsd1.ca.comcast.net] has quit [Ping timeout: 240 seconds]14:22
-!- danielsocials [~quassel@45.32.248.113] has joined #bitcoin-wizards14:23
-!- MoALTz [~no@78-11-180-214.static.ip.netia.com.pl] has joined #bitcoin-wizards14:23
-!- danielsocials [~quassel@45.32.248.113] has quit [Remote host closed the connection]14:25
-!- tjader [~tjader@189.60.215.244] has quit [Ping timeout: 276 seconds]14:30
-!- Guest84113 [sid105317@gateway/web/irccloud.com/x-zossjnuukpdvfgyt] has quit []14:34
-!- tjader [~tjader@189.60.215.244] has joined #bitcoin-wizards14:34
-!- Guest84113 [sid105317@gateway/web/irccloud.com/x-unincutozuxtnrts] has joined #bitcoin-wizards14:35
-!- Guest84113 [sid105317@gateway/web/irccloud.com/x-unincutozuxtnrts] has quit [Client Quit]14:35
-!- wbinns [sid105317@gateway/web/irccloud.com/x-hhfpjyfeuhqxwhty] has joined #bitcoin-wizards14:35
-!- wbinns [sid105317@gateway/web/irccloud.com/x-hhfpjyfeuhqxwhty] has quit [Client Quit]14:35
-!- sCOGSBY [~uumdbmd@173.44.55.98] has joined #bitcoin-wizards14:36
-!- phiche1 [~Adium@fr03.vpn.ht] has joined #bitcoin-wizards14:37
-!- phiche [~Adium@37.250.46.20.bredband.tre.se] has quit [Ping timeout: 260 seconds]14:38
-!- roman [~quassel@ANice-652-1-257-247.w86-203.abo.wanadoo.fr] has joined #bitcoin-wizards14:39
-!- belcher [~user@unaffiliated/belcher] has joined #bitcoin-wizards14:43
-!- erasmospunk [~erasmospu@151.41.84.55] has joined #bitcoin-wizards14:45
-!- adam3us [~Adium@172.56.38.20] has joined #bitcoin-wizards14:51
-!- phiche [~Adium@37.250.46.20.bredband.tre.se] has joined #bitcoin-wizards14:51
-!- ozanyurt_ [~textual@151.250.35.143] has quit [Quit: Textual IRC Client: www.textualapp.com]14:51
-!- phiche1 [~Adium@fr03.vpn.ht] has quit [Ping timeout: 250 seconds]14:53
-!- yorick [~yorick@oftn/member/yorick] has quit [Quit: quit.]14:54
-!- yorick [~yorick@ip51cd0513.speed.planet.nl] has joined #bitcoin-wizards14:56
-!- yorick [~yorick@ip51cd0513.speed.planet.nl] has quit [Changing host]14:56
-!- yorick [~yorick@oftn/member/yorick] has joined #bitcoin-wizards14:56
-!- Guyver2 [~Guyver2@guyver2.xs4all.nl] has quit [Remote host closed the connection]15:01
-!- erasmospunk [~erasmospu@151.41.84.55] has quit [Remote host closed the connection]15:02
-!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has quit [Quit: Leaving.]15:02
-!- dnaleor [~dnaleor@78-23-74-78.access.telenet.be] has quit [Remote host closed the connection]15:03
-!- OneFixt [~OneFixt@unaffiliated/onefixt] has joined #bitcoin-wizards15:06
-!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has joined #bitcoin-wizards15:07
-!- arowser [~quassel@106.120.101.38] has quit [Quit: No Ping reply in 180 seconds.]15:07
-!- arowser [~quassel@106.120.101.38] has joined #bitcoin-wizards15:08
-!- phiche [~Adium@37.250.46.20.bredband.tre.se] has quit [Quit: Leaving.]15:09
-!- dnaleor [~dnaleor@78-23-74-78.access.telenet.be] has joined #bitcoin-wizards15:11
-!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has quit [Client Quit]15:11
-!- memymo [~textual@184-23-239-227.dedicated.static.sonic.net] has quit [Quit: My Mac has gone to sleep. ZZZzzz…]15:13
-!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has joined #bitcoin-wizards15:16
-!- NewLiberty [~NewLibert@rrcs-74-87-213-251.west.biz.rr.com] has joined #bitcoin-wizards15:20
-!- OneFixt [~OneFixt@unaffiliated/onefixt] has quit [Remote host closed the connection]15:23
-!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has quit [Quit: Leaving.]15:27
-!- rustyn [~rustyn@unaffiliated/rustyn] has quit [Quit: rar]15:29
-!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has joined #bitcoin-wizards15:29
-!- dEBRUYNE_ [~dEBRUYNE@56-197-ftth.onsbrabantnet.nl] has joined #bitcoin-wizards15:29
-!- murch [~murch@p4FE394A2.dip0.t-ipconnect.de] has left #bitcoin-wizards []15:31
-!- dEBRUYNE [~dEBRUYNE@56-197-ftth.onsbrabantnet.nl] has quit [Ping timeout: 256 seconds]15:32
-!- dcousens [~anon@1.136.96.213] has quit [Read error: Connection reset by peer]15:36
-!- dnaleor [~dnaleor@78-23-74-78.access.telenet.be] has quit [Remote host closed the connection]15:38
-!- Erik_dc [~erik@d54c620ed.access.telenet.be] has quit [Remote host closed the connection]15:40
-!- dcousens [~anon@1.136.96.213] has joined #bitcoin-wizards15:40
-!- adam3us [~Adium@172.56.38.20] has quit [Quit: Leaving.]15:41
-!- moa [~kiwigb@opentransactions/dev/moa] has joined #bitcoin-wizards15:44
-!- DougieBot5000 [~DougieBot@unaffiliated/dougiebot5000] has quit [Quit: Leaving]15:48
-!- GGuyZ [~GGuyZ@216-15-125-203.c3-0.sbo-ubr1.sbo.ma.cable.rcn.com] has joined #bitcoin-wizards15:50
-!- sausage_factory is now known as priidu15:57
-!- zooko [~user@72.42.70.227] has quit [Ping timeout: 272 seconds]15:57
-!- ThomasV [~ThomasV@unaffiliated/thomasv] has joined #bitcoin-wizards15:57
-!- tjader [~tjader@189.60.215.244] has quit [Ping timeout: 276 seconds]16:00
-!- tjader [~tjader@189.60.215.244] has joined #bitcoin-wizards16:04
-!- ThomasV [~ThomasV@unaffiliated/thomasv] has quit [Ping timeout: 256 seconds]16:05
-!- nonaTure [~happy@179.43.176.98] has quit [Quit: Leaving.]16:07
-!- Jeremy_Rand_2 [~user@ip68-97-38-24.ok.ok.cox.net] has joined #bitcoin-wizards16:14
-!- dnaleor [~dnaleor@78-23-74-78.access.telenet.be] has joined #bitcoin-wizards16:18
-!- GGuyZ [~GGuyZ@216-15-125-203.c3-0.sbo-ubr1.sbo.ma.cable.rcn.com] has quit [Read error: Connection reset by peer]16:18
-!- AndChat|435584 [~AndChat43@103.239.235.30] has joined #bitcoin-wizards16:18
-!- GGuyZ [~GGuyZ@216-15-125-203.c3-0.sbo-ubr1.sbo.ma.cable.rcn.com] has joined #bitcoin-wizards16:18
-!- MrChrisJ_ [~MrChrisJ@host86-128-121-45.range86-128.btcentralplus.com] has joined #bitcoin-wizards16:19
-!- skyraider_ [uid41097@gateway/web/irccloud.com/x-hzzzjzviabokeiok] has quit [Quit: Connection closed for inactivity]16:20
-!- MrChrisJ_ [~MrChrisJ@host86-128-121-45.range86-128.btcentralplus.com] has quit [Client Quit]16:20
-!- MrChrisJ [~MrChrisJ@host86-128-121-45.range86-128.btcentralplus.com] has quit [Ping timeout: 256 seconds]16:21
-!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has quit [Quit: Leaving.]16:23
-!- RoboTedd_ [~roboteddy@c-67-188-40-206.hsd1.ca.comcast.net] has joined #bitcoin-wizards16:28
-!- RoboTeddy [~roboteddy@c-67-188-40-206.hsd1.ca.comcast.net] has quit [Ping timeout: 265 seconds]16:31
-!- memymo [~textual@c-24-4-69-49.hsd1.ca.comcast.net] has joined #bitcoin-wizards16:32
-!- mkarrer_ [~mkarrer@211.Red-2-138-29.dynamicIP.rima-tde.net] has quit [Remote host closed the connection]16:35
-!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has joined #bitcoin-wizards16:36
-!- dcousens [~anon@1.136.96.213] has quit [Ping timeout: 264 seconds]16:38
-!- chjj [~chjj@unaffiliated/chjj] has quit [Quit: null]16:43
-!- chjj [~chjj@unaffiliated/chjj] has joined #bitcoin-wizards16:43
-!- chjj [~chjj@unaffiliated/chjj] has quit [Client Quit]16:45
-!- tjader [~tjader@189.60.215.244] has quit [Ping timeout: 276 seconds]16:45
-!- chjj [~chjj@unaffiliated/chjj] has joined #bitcoin-wizards16:47
-!- tjader [~tjader@189.60.215.244] has joined #bitcoin-wizards16:50
-!- markus-k_ [~markus-k@p5499544C.dip0.t-ipconnect.de] has joined #bitcoin-wizards16:58
-!- mrkent [~textual@unaffiliated/mrkent] has joined #bitcoin-wizards16:58
-!- markus-k_ [~markus-k@p5499544C.dip0.t-ipconnect.de] has quit [Max SendQ exceeded]17:00
-!- voxelot [~voxelot@remote.digitalmoneycorp.com] has quit [Ping timeout: 240 seconds]17:03
-!- TheSeven [~quassel@rockbox/developer/TheSeven] has quit [Ping timeout: 240 seconds]17:07
-!- GGuyZ [~GGuyZ@216-15-125-203.c3-0.sbo-ubr1.sbo.ma.cable.rcn.com] has quit [Quit: GGuyZ]17:09
-!- polyclef [~polyclef@184-23-239-227.dedicated.static.sonic.net] has quit [Ping timeout: 265 seconds]17:13
-!- roman [~quassel@ANice-652-1-257-247.w86-203.abo.wanadoo.fr] has quit [Remote host closed the connection]17:14
-!- TheSeven [~quassel@rockbox/developer/TheSeven] has joined #bitcoin-wizards17:16
-!- bobke [~bobke@d51536036.access.telenet.be] has joined #bitcoin-wizards17:16
-!- brg444 [18257df2@gateway/web/freenode/ip.24.37.125.242] has quit [Quit: Page closed]17:17
-!- kang_ [67efeb1e@gateway/web/freenode/ip.103.239.235.30] has joined #bitcoin-wizards17:18
-!- BananaLotus [~BananaLot@54.186.186.141] has quit [Remote host closed the connection]17:22
-!- guruvan [~guruvan@unaffiliated/guruvan] has quit [Remote host closed the connection]17:22
-!- kefkius [~kefkius@unaffiliated/kefkius] has quit [Remote host closed the connection]17:22
-!- arowser [~quassel@106.120.101.38] has quit [Quit: No Ping reply in 180 seconds.]17:24
-!- arowser [~quassel@106.120.101.38] has joined #bitcoin-wizards17:24
-!- Giszmo [~leo@pc-139-55-215-201.cm.vtr.net] has quit [Ping timeout: 272 seconds]17:25
-!- alpalp [~alp@104-54-235-28.lightspeed.austtx.sbcglobal.net] has quit [Remote host closed the connection]17:29
-!- AaronvanW [~ewout@unaffiliated/aaronvanw] has quit [Read error: Connection reset by peer]17:34
-!- AaronvanW [~ewout@unaffiliated/aaronvanw] has joined #bitcoin-wizards17:35
-!- danielsocials [~quassel@45.32.248.113] has joined #bitcoin-wizards17:37
-!- danielsocials [~quassel@45.32.248.113] has quit [Remote host closed the connection]17:38
-!- memymo [~textual@c-24-4-69-49.hsd1.ca.comcast.net] has quit [Quit: My Mac has gone to sleep. ZZZzzz…]17:41
-!- GGuyZ [~GGuyZ@216-15-125-203.c3-0.sbo-ubr1.sbo.ma.cable.rcn.com] has joined #bitcoin-wizards17:41
-!- alpalp [~alp@unaffiliated/alpalp] has joined #bitcoin-wizards17:42
-!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has quit [Quit: Leaving.]17:45
-!- adam3us [~Adium@184-23-239-227.dedicated.static.sonic.net] has joined #bitcoin-wizards17:46
-!- adam3us [~Adium@184-23-239-227.dedicated.static.sonic.net] has quit [Client Quit]17:46
-!- adam3us [~Adium@184-23-239-227.dedicated.static.sonic.net] has joined #bitcoin-wizards17:46
-!- funkenstein_ [~bowler@unaffiliated/funkenstein] has joined #bitcoin-wizards17:51
-!- oneeman [~oneeman@ip48-68-15-186.ct.co.cr] has joined #bitcoin-wizards17:51
-!- dnaleor [~dnaleor@78-23-74-78.access.telenet.be] has quit [Quit: Leaving]18:03
-!- GGuyZ [~GGuyZ@216-15-125-203.c3-0.sbo-ubr1.sbo.ma.cable.rcn.com] has quit [Quit: GGuyZ]18:04
-!- kyletorpey [~kyle@pool-74-110-148-103.rcmdva.fios.verizon.net] has joined #bitcoin-wizards18:08
-!- Giszmo [~leo@2001:470:7ca1:ff81:120b:a9ff:fe07:1c8] has joined #bitcoin-wizards18:08
-!- dnaleor [~dnaleor@78-23-74-78.access.telenet.be] has joined #bitcoin-wizards18:09
-!- Giszmo [~leo@2001:470:7ca1:ff81:120b:a9ff:fe07:1c8] has quit [Ping timeout: 240 seconds]18:12
-!- kyletorpey [~kyle@pool-74-110-148-103.rcmdva.fios.verizon.net] has left #bitcoin-wizards []18:13
-!- tjader [~tjader@189.60.215.244] has quit [Ping timeout: 276 seconds]18:15
-!- moa [~kiwigb@opentransactions/dev/moa] has quit [Quit: Leaving.]18:18
-!- tjader [~tjader@189.60.215.244] has joined #bitcoin-wizards18:20
-!- roconnor [~roconnor@host-45-58-255-91.dyn.295.ca] has joined #bitcoin-wizards18:24
gmaxwelltromp_: CONGRATS ON L19 computation!18:27
-!- binns [sid105317@gateway/web/irccloud.com/x-ykhjlintuvnsbqdt] has joined #bitcoin-wizards18:30
-!- binns is now known as Guest1996818:30
-!- Guest19968 [sid105317@gateway/web/irccloud.com/x-ykhjlintuvnsbqdt] has quit [Changing host]18:33
-!- Guest19968 [sid105317@unaffiliated/gwb3] has joined #bitcoin-wizards18:33
-!- Guest19968 [sid105317@unaffiliated/gwb3] has quit [Changing host]18:33
-!- Guest19968 [sid105317@gateway/web/irccloud.com/x-ykhjlintuvnsbqdt] has joined #bitcoin-wizards18:33
-!- Guest19968 is now known as binns18:33
-!- GGuyZ [~GGuyZ@216-15-125-203.c3-0.sbo-ubr1.sbo.ma.cable.rcn.com] has joined #bitcoin-wizards18:35
-!- Giszmo [~leo@pc-139-55-215-201.cm.vtr.net] has joined #bitcoin-wizards18:35
-!- binns is now known as wbinns18:35
-!- wbinns is now known as binns18:35
-!- go1111111 [~go1111111@104.232.116.217] has quit [Ping timeout: 260 seconds]18:39
-!- binns [sid105317@gateway/web/irccloud.com/x-ykhjlintuvnsbqdt] has quit [Quit: Updating details, brb]18:48
-!- binns [sid105317@gateway/web/irccloud.com/x-jckkcjeodjtmuiax] has joined #bitcoin-wizards18:48
-!- go1111111 [~go1111111@104.200.154.52] has joined #bitcoin-wizards18:53
tromp_thanks, Gregory!18:54
-!- AaronvanW [~ewout@unaffiliated/aaronvanw] has quit [Ping timeout: 250 seconds]18:54
-!- arowser [~quassel@106.120.101.38] has quit [Quit: No Ping reply in 180 seconds.]18:55
-!- danielsocials [~quassel@45.32.248.113] has joined #bitcoin-wizards18:55
-!- arowser [~quassel@106.120.101.38] has joined #bitcoin-wizards18:55
-!- bityogi [~textual@208-104-143-200.brvd.dsl.dyn.comporium.net] has quit [Quit: My Mac has gone to sleep. ZZZzzz…]18:58
bsm1175321Whazzat?18:59
tromp_https://news.ycombinator.com/item?id=1095087518:59
bsm1175321Darn.  There goes my PoW algorithm...19:00
tromp_perfect for a 9 month block interval:-)19:00
bsm1175321Hey, if my landlord accepts yearly rent...19:01
-!- adam3us [~Adium@184-23-239-227.dedicated.static.sonic.net] has quit [Quit: Leaving.]19:02
bsm1175321I actually typed: isprime(2**74207281-1) into Maple today.  Perhaps I was over-optimistic.19:03
bsm1175321there must be special techniques for merseinne primes...19:04
-!- sCOGSBY [~uumdbmd@173.44.55.98] has quit [Remote host closed the connection]19:04
-!- chjj_ [~chjj@unaffiliated/chjj] has joined #bitcoin-wizards19:04
-!- gavink [~g@184.75.223.211] has quit [Ping timeout: 245 seconds]19:09
tromp_i think it's called the lucas-lehmer test19:11
-!- chjj_ [~chjj@unaffiliated/chjj] has quit [Quit: null]19:11
-!- bramc [~bram@216.216.202.69] has joined #bitcoin-wizards19:11
bramcOkay, so I'm partway into writing the insertion code now, and somewhat unrelatedly have run into a bit of a moral dilemma19:12
-!- dnaleor [~dnaleor@78-23-74-78.access.telenet.be] has quit [Quit: Leaving]19:14
bramcFor fairly obvious reasons it's much faster to check for inclusion in a hashtable than in a tree, so when doing significant inclusion checking operations it's a good idea to have a parallel standard set for doing those operations. Some goes if you want a map.19:15
-!- binns [sid105317@gateway/web/irccloud.com/x-jckkcjeodjtmuiax] has quit [Quit: Updating details, brb]19:17
bramcSo there's this ridiculous is_included() method sitting here. On the one hand, someone might have a good reason for using it in case of emergency. On the other hand, it's inclusion would seem to imply that it's a good idea to use it. I'm tempted to remove it completely. What does everybody think?19:17
-!- binns [sid105317@gateway/web/irccloud.com/x-ltecridgvwreosnw] has joined #bitcoin-wizards19:17
bsm1175321You really want this fast, don't you?19:17
bsm1175321log(n) vs O(1) is a good problem to have.19:18
bramcThe method is_included_make_proof() of course stays. The advantage of is_included() is that it's much more performant, but nowhere near as performant as the same call on a normal set is.19:18
bsm1175321I'm wrestling with O(n^3) on some braid algorithms.19:18
-!- Guest75253 is now known as mr_burdell19:18
-!- o3u is now known as Fistful_of_Coins19:18
-!- mr_burdell [~mr_burdel@bounce.cryptolabs.net] has quit [Changing host]19:18
-!- mr_burdell [~mr_burdel@unaffiliated/mr-burdell/x-7609603] has joined #bitcoin-wizards19:18
bramcbsm117532 It's already log(n), The whole point of this exercise is to get cache misses from log(n) to log(log(n)). Constant factors matter.19:18
-!- funkenstein_ [~bowler@unaffiliated/funkenstein] has left #bitcoin-wizards ["Leaving"]19:19
bramcTechnically log(log(n)) isn't a constant factor, but it acts a lot like it in practice.19:19
bsm1175321Hashes should be O(1) no?  You're probably using a more sophisticated analysis of the buckets than me...19:19
bramcYes hashes are O(1). It's my set which is O(log(log(n))19:20
bramc)19:20
bsm1175321Uh...How did you add another log?19:20
bramcThe location of nodes in memory is set up so that they're near each other.19:21
bramcIn the case of is_included() it skips to the bottom of a block directly thus avoiding a bunch of lookups, making its behavior much closer to that of a hashtable.19:21
-!- voxelot [~voxelot@cpe-76-168-143-16.socal.res.rr.com] has joined #bitcoin-wizards19:21
bramcAt least, it does that for balanced blocks. Basically it's treating balanced blocks as hashtables, which is a fairly accurate description of them19:22
bsm1175321So it's a binary tree, which is log(n) in general, or O(1) modulo bucket reallcation... Explain how memory locality is modifying this?19:22
bsm1175321What is a "block" in this context?19:23
bramcThe fanout within a block is limited, it only goes so many levels deep before pointing to another block19:23
-!- danielsocials [~quassel@45.32.248.113] has quit [Remote host closed the connection]19:24
bsm1175321I see, so the n of the block-based algorithm is log(n) for the blocks.19:24
bsm1175321Wait, that can't work...19:25
bramcSo a block might represent, say, 5 bits. If you're doing a lookup at, say, 33 bits, you'll have cache misses at bits 4, 9, 14, 19, 24, 29, and then you're in a leaf so there are lookups for 30, 31, 32, and 33, but they're probably all in close memory proximity because they're in the same block.19:26
bsm1175321The cache size shouldn't turn it from O(log(n)) to O(log(log n)) butt it might turn it into O((cache)*log(n/cache)), no?19:26
-!- NewLiberty [~NewLibert@rrcs-74-87-213-251.west.biz.rr.com] has quit [Ping timeout: 250 seconds]19:26
bramcMy brain is too addled from writing 100 lines of code just now to make such subtle distinctions. There are ugly practicalities in this code.19:27
bsm1175321I'm afraid you know a lot more about caches than me.19:27
bramcThe l1 and l2 cache are fairly simple. If you do a lookup to a place in memory too far from any of the places you've recently looked, you have to wait for it to be swapped into cache, which is fairly expensive.19:28
bramcSome concept as disk accesses, but smaller distances and smaller times.19:28
bsm1175321I guess my argument is that if you have an O(log(n)) algorithm (a binary tree), and you play caching games, this can't possibly get it to O(log(log(n))), can it?  It can just insert funny constant factors, but not another log.19:29
bsm1175321If I graphed it, it should be A*log(n) + B*log(n) + C*log(n) as n gets larget, with discrete jumps between A,B,C as the caches get full, no?19:30
bsm1175321*larger19:30
-!- Burrito [~Burrito@unaffiliated/burrito] has quit [Quit: Leaving]19:30
bsm1175321Jumps due to the speed of the caches.19:30
bramcThe tricks are that (a) branch blocks are in fixed position, so you can jump to the place where they point out most of the time, (b) everything within a block is in close proximity, so you can traverse the whole thing with possibly only a single cache miss19:33
bramcI'm of course not directly referencing caches in my code. Just doing really weird-looking manual memory management to behave well with them.19:33
bramcMostly I have a giant byte array called self.memory19:34
bsm1175321Shouldn't this just smooth out the transition between size(L1), size(L2), and size(L3) rather than make it log log?19:35
bsm1175321I mean, the asymptotic limit, for a very large set, the cache doesn't help, no?19:36
bramcCaches don't exactly get full. The simple model is to imagine that the computer has a small number of caches of fixed size: Say 16 of size 16 kilobytes, and whenever a part of memory is pulled in it's either part of one of the last 16 or the general neighborhood of size 16 kilobytes gets pulled into cache, and the least recently used gets booted.19:36
bramcSo if you can be very clever about making memory lookups have a lot of local affinity things can be very fast. Tree operations tend to bottleneck on waiting for memory.19:37
bsm1175321I'd think it would be e.g. B*log(n/b) to find the block plus A*log(n/a) within the bloc, for example, for an overall B*log(n/b) + A*log(n/a) = (A+B)*log(n) - B log b - A log a...19:37
bsm1175321So the cache is adding constant factors and modifying the coefficient of the log.19:38
bramcNo blocks are indexed by position, pulling data from one is a single cache miss19:38
bsm1175321It sounds to me like your locality argument is increasing the "effective size" of the cache. No?19:39
bramcUh, sort of. The root block gets pulled in first, then you go several bits deep without having to leave that block, then you get referred to another block, which is of course a cache miss, which leads you a few more bits deep, then refers to another block...19:41
-!- mrkent [~textual@unaffiliated/mrkent] has quit []19:41
-!- rusty [~rusty@pdpc/supporter/bronze/rusty] has joined #bitcoin-wizards19:42
bramcThere's a big difference between branch and leaf blocks, in that branch blocks are balanced and fixed position while leaf blocks do dynamic memory allocation using append to the end and sweep once they hit the end19:43
bramcof the block19:43
-!- NewLiberty [~NewLibert@2602:306:b8e0:8160:1d24:166b:c99f:bb49] has joined #bitcoin-wizards19:43
bsm1175321So I'd argue that there's a range of set sizes where these optimizations are important.  e.g. with 16 caches of 16kb it smooths out the log curve of a < 16kb set to one of 256kb which is entirely in the L2 cache.  Likewise a smoother transition from L2 to L3. So what is your use case, and do you expect the set size to be in a range where these optimizations will make a big difference?19:43
bramcThis is for the utxo set, which I think is about 200 million entries, although maybe I just made that number up19:44
bsm1175321So much larger than the largest cache around.19:44
bsm1175321And growing :-19:45
bsm1175321:-(19:45
bramcYes vastly larger.19:45
-!- tjader [~tjader@189.60.215.244] has quit [Ping timeout: 276 seconds]19:45
bsm1175321Are you sure these optimizations are noticeable on a set size very much larger than the cache?19:45
bramcThe TODOs at the top of this file are terrifying. Starting with porting to C.19:45
bsm1175321heheee19:45
bramcThey matter more the larger the set size is19:46
bsm1175321I think you're changing the coefficient of the log A*log(n)19:46
bramcThe trick is to make the block size reasonable. I have that as a parameter, it goes up by (roughly) factors of 2.19:46
bramcIf the block size is too big it gets cache misses within block, if it's too small there are cache misses elsewhere.19:46
bsm1175321Ok I have no doubt these kinds of optimizations could change A by a factor 2 or more.19:47
bramcMy computer's about to die, have to leave the coffee shop and head home, be back in a bit.19:47
bramcI'm guessing my implementation will be about a factor of 4 better than a simple one. It could easily be anywhere in the range 2-20 though.19:48
-!- Ylbam [uid99779@gateway/web/irccloud.com/x-cyyaujocdjepnyyn] has quit [Quit: Connection closed for inactivity]19:48
-!- bramc [~bram@216.216.202.69] has quit [Quit: This computer has gone to sleep]19:48
-!- jtimon [~quassel@126.31.134.37.dynamic.jazztel.es] has quit [Ping timeout: 250 seconds]19:50
-!- tjader [~tjader@189.60.215.244] has joined #bitcoin-wizards19:51
-!- mihar [~mihar@4.16.87.162] has quit [Ping timeout: 276 seconds]19:55
-!- dEBRUYNE_ [~dEBRUYNE@56-197-ftth.onsbrabantnet.nl] has quit [Quit: Leaving]19:57
-!- NewLiberty [~NewLibert@2602:306:b8e0:8160:1d24:166b:c99f:bb49] has quit [Ping timeout: 240 seconds]19:57
bsm1175321;;tell bramc Wait I see.  In a block of blocks, that can be entirely loaded into the cache, you can search for the next sub-block.  And a sub-block fits within the cache. So in principle the search could be composed from (# cache loads)*(log(cache size)) + (# cache loads)*(cache load time)19:58
gribbleError: I haven't seen bramc, I'll let you do the telling.19:58
bsm1175321wtf19:58
-!- adam3us [~Adium@172.56.39.50] has joined #bitcoin-wizards20:00
-!- bramc [~bram@99-75-88-206.lightspeed.sntcca.sbcglobal.net] has joined #bitcoin-wizards20:02
-!- brg444 [4631ca01@gateway/web/freenode/ip.70.49.202.1] has joined #bitcoin-wizards20:02
-!- zmachine [~zmachine@pool-74-100-90-30.lsanca.fios.verizon.net] has quit [Ping timeout: 265 seconds]20:02
-!- BananaLotus [~BananaLot@54.186.186.141] has joined #bitcoin-wizards20:02
bramcbsm117532 I think that's right although my brain is jello at the moment20:03
-!- guruvan [~guruvan@unaffiliated/guruvan] has joined #bitcoin-wizards20:03
bsm1175321Which is A*log(# caches)*log(n) + const20:06
bsm1175321Well, cool, nonetheless, to give L1 cache speed to a much larger data structure.  :-)20:06
-!- TheSeven [~quassel@rockbox/developer/TheSeven] has quit [Ping timeout: 245 seconds]20:07
bsm1175321Have a good night.  I'll make you do O(n) analysis on graph algorithms when you least expect it!  ;-)20:07
-!- zmachine [~zmachine@pool-74-100-90-30.lsanca.fios.verizon.net] has joined #bitcoin-wizards20:08
-!- GGuyZ [~GGuyZ@216-15-125-203.c3-0.sbo-ubr1.sbo.ma.cable.rcn.com] has quit [Quit: GGuyZ]20:08
-!- TheSeven [~quassel@rockbox/developer/TheSeven] has joined #bitcoin-wizards20:08
-!- GGuyZ [~GGuyZ@216-15-125-203.c3-0.sbo-ubr1.sbo.ma.cable.rcn.com] has joined #bitcoin-wizards20:12
-!- adam3us [~Adium@172.56.39.50] has quit [Quit: Leaving.]20:15
-!- rusty [~rusty@pdpc/supporter/bronze/rusty] has quit [Ping timeout: 272 seconds]20:18
-!- oneeman [~oneeman@ip48-68-15-186.ct.co.cr] has quit [Quit: Leaving]20:18
-!- sparetire [~sparetire@unaffiliated/sparetire] has quit [Quit: sparetire]20:19
-!- danielsocials [~quassel@45.32.248.113] has joined #bitcoin-wizards20:24
-!- NewLiberty [~NewLibert@2602:306:b8e0:8160:1d24:166b:c99f:bb49] has joined #bitcoin-wizards20:25
-!- brg444 [4631ca01@gateway/web/freenode/ip.70.49.202.1] has quit [Ping timeout: 252 seconds]20:41
-!- ttttemp [~ttttemp@pc-5305.ethz.ch] has quit [Remote host closed the connection]20:42
-!- danielsocials [~quassel@45.32.248.113] has quit [Remote host closed the connection]20:43
-!- ttttemp [~ttttemp@pc-10236.ethz.ch] has joined #bitcoin-wizards20:44
-!- belcher [~user@unaffiliated/belcher] has quit [Quit: Leaving]20:45
-!- memymo [~textual@c-24-4-69-49.hsd1.ca.comcast.net] has joined #bitcoin-wizards20:47
-!- voxelot [~voxelot@cpe-76-168-143-16.socal.res.rr.com] has quit [Ping timeout: 265 seconds]20:52
-!- voxelot [~voxelot@2606:6000:6783:ff00:29e9:c182:4700:c755] has joined #bitcoin-wizards21:04
-!- priidu [~priidu@unaffiliated/priidu] has quit [Ping timeout: 276 seconds]21:09
-!- justanotheruser [~Justan@unaffiliated/justanotheruser] has quit [Read error: Connection reset by peer]21:11
-!- justanotheruser [~Justan@unaffiliated/justanotheruser] has joined #bitcoin-wizards21:13
-!- tjader [~tjader@189.60.215.244] has quit [Ping timeout: 276 seconds]21:17
-!- tjader [~tjader@189.60.215.244] has joined #bitcoin-wizards21:21
-!- RoboTedd_ [~roboteddy@c-67-188-40-206.hsd1.ca.comcast.net] has quit [Remote host closed the connection]21:33
-!- RoboTeddy [~roboteddy@c-67-188-40-206.hsd1.ca.comcast.net] has joined #bitcoin-wizards21:34
-!- NewLiberty [~NewLibert@2602:306:b8e0:8160:1d24:166b:c99f:bb49] has quit [Ping timeout: 260 seconds]21:39
-!- p15 [~p15@90.91.145.64.client.static.strong-tk2.bringover.net] has joined #bitcoin-wizards21:41
-!- ttttemp_ [~ttttemp@nb-10350.ethz.ch] has joined #bitcoin-wizards21:42
-!- kang_ [67efeb1e@gateway/web/freenode/ip.103.239.235.30] has left #bitcoin-wizards []21:46
-!- adam3us [~Adium@216.9.110.6] has joined #bitcoin-wizards21:54
-!- voxelot [~voxelot@2606:6000:6783:ff00:29e9:c182:4700:c755] has quit [Ping timeout: 250 seconds]21:58
-!- mpmcsweeney [~mpmcsween@pool-71-174-112-117.bstnma.fios.verizon.net] has joined #bitcoin-wizards22:07
-!- mpmcsweeney [~mpmcsween@pool-71-174-112-117.bstnma.fios.verizon.net] has quit [Client Quit]22:07
-!- voxelot [~voxelot@2606:6000:6783:ff00:29e9:c182:4700:c755] has joined #bitcoin-wizards22:08
-!- GreenIsMyPepper [~GreenIsMy@2605:6400:20:11aa:189e:28a5:52ed:8948] has quit [Ping timeout: 250 seconds]22:08
-!- GreenIsMyPepper [~GreenIsMy@2605:6400:20:11aa:189e:28a5:52ed:8948] has joined #bitcoin-wizards22:10
Luke-Jrrandom idea: would it cost much for blocks to commit to the heights of each tx input? this would be to make it possible to fraud-proof that inputs don't exist22:34
Luke-Jr(maybe possible to bundle into segwit?)22:34
-!- voxelot [~voxelot@2606:6000:6783:ff00:29e9:c182:4700:c755] has quit [Ping timeout: 260 seconds]22:40
-!- dcousens [~anon@c110-22-219-15.sunsh4.vic.optusnet.com.au] has joined #bitcoin-wizards22:41
-!- zzyzx [~chatzilla@97-90-24-187.dhcp.mtpk.ca.charter.com] has quit [Quit: ChatZilla 0.9.92 [SeaMonkey 2.39/20151103191810]]22:46
-!- bit2017 [~linker@27.75.174.138] has joined #bitcoin-wizards22:47
-!- nivah [~linker@27.75.174.138] has quit [Ping timeout: 264 seconds]22:48
-!- voxelot [~voxelot@2606:6000:6783:ff00:29e9:c182:4700:c755] has joined #bitcoin-wizards22:52
-!- adam3us [~Adium@216.9.110.6] has quit [Quit: Leaving.]22:55
-!- T23WS [~textual@45.56.159.18] has joined #bitcoin-wizards22:56
-!- GGuyZ [~GGuyZ@216-15-125-203.c3-0.sbo-ubr1.sbo.ma.cable.rcn.com] has quit [Quit: GGuyZ]22:58
-!- T23WS [~textual@45.56.159.18] has quit [Client Quit]22:59
-!- DougieBot5000 [~DougieBot@unaffiliated/dougiebot5000] has joined #bitcoin-wizards23:33
-!- nonaTure [~happy@94.155.72.86] has joined #bitcoin-wizards23:44
-!- ThomasV [~ThomasV@unaffiliated/thomasv] has joined #bitcoin-wizards23:44
-!- voxelot [~voxelot@2606:6000:6783:ff00:29e9:c182:4700:c755] has quit [Ping timeout: 260 seconds]23:54
-!- Ylbam [uid99779@gateway/web/irccloud.com/x-mkgqjnimkhhfujcj] has joined #bitcoin-wizards23:58
--- Log closed Sat Jan 23 00:00:12 2016

Generated by irclog2html.py 2.15.0.dev0 by Marius Gedminas - find it at mg.pov.lt!