Meta tags:
author= Gwern, FeepingCreature, nshepperd, Khoth;
description= Timothy Falcon’s quantitative-finance interview problem #14 asks for the optimal stopping strategy when playing a card-drawing game of 𝑙 cards where red = +$1 & black = −$1; the value approaches 0.5 × √𝑙. I re-solve it with dynamic programming in R, and others in Neat, Haskell & C, with increasing efficiency.;
keywords= cs/c, cs/haskell, cs/r, statistics/decision;
Headings (most frequently used words):
dynamic, programming, dp, bottom, up, neat, array, blocks, problem, 14, solutions, non, optimal, stopping, version, spreadsheet, answer, top, down, faster, approximating, backlinks, similar, links, bibliography, haskell, parallel, simulation, check, diagonal, diagonalization, skipping,
Text of the page (most frequently used words):
the (234), int (184), cards (98), value (73), and (67), for (67), dia (65), work (58), return (53), good (47), that (43), thread (38), bad (35), with (34), you (34), red (34), can (33), black (33), void (31), this (30), rem_black (30), rem_red (29), float (29), count (28), include (28), winnings (26), state (26), prevdia (25), num_blocks (24), define (24), threads (23), problem (22), prev_dia (22), cash (22), block_size (22), like (21), which (21), else (21), one (20), are (20), optimal (20), card (20), work_item_t (20), config (20), data (19), version (18), cur (18), time (17), bool (17), max (17), because (17), step (17), col (16), row (16), error (15), values (15), game (15), khoth (14), but (14), 000 (14), expected (14), limit (14), base_r (14), cur_dia (14), bottom (14), payoff (14), ascent (14), curdia (14), array (14), while (13), 22e (13), square (13), root (13), feepingcreature (13), base_b (13), will (13), approximation (12), has (12), all (12), states (12), programming (12), struct (12), each (12), then (11), log (11), true (11), size (11), not (11), table (11), there (11), only (11), cpu (11), r0_edge (11), num_threads (11), b0_edge (11), main (11), blocks (11), auto (11), clang (10), out (10), std (10), exact (10), space (10), possible (10), from (10), faster (10), core (10), num_cards (10), value_if_stop (10), value_if_go (10), diag_arr (10), head (10), tail (10), pred (10), active (10), import (10), dynamic (10), rounds (10), diagonal (9), down (9), spreadsheet (9), when (9), calc (9), dia1 (9), dia2 (9), configs (9), tab (9), dpcalc (9), expectedvalue (9), key (9), null (8), some (8), gcc (8), multiple (8), squared (8), sqrt (8), frame (8), 100 (8), double (8), block (8), than (8), done_sem (8), put_work (8), work_sem (8), r_ix (8), b_ix (8), work_queue_len (8), stdio (8), look (8), pblack (8), false (8), threadconfig (8), outcome (8), play (8), playpayoff (8), winning (8), stopping (8), what (7), would (7), enough (7), deck (7), could (7), type (7), final (7), draw (7), more (7), they (7), where (7), printf (7), r_progress (7), must (7), stop (7), much (7), how (7), evaluation (7), using (7), blacks (7), haskell (7), mut (7), function (7), neat (7), cache (7), playing (7), links (6), used (6), 165 (6), pthread (6), case (6), volatile (6), intercept (6), small (6), probability (6), problems (6), estimate (6), min (6), initial (6), have (6), before (6), into (6), parallel (6), implementation (6), calculate (6), block_b (6), put_work_mutex (6), b_progress (6), work_queue (6), get (6), ret (6), grab_work_mutex (6), triangle (6), code (6), bool_set_spin (6), bool_wait_spin (6), drawn (6), dia_from (6), dia_to (6), malloc (6), sizeof (6), math (6), evaluate (6), any (6), tmp (6), still (6), solve (6), new (6), top (6), montecarlo (6), simulation (6), similar (5), backlinks (5), think (5), performance (5), native (5), use (5), march (5), ofast (5), optimization (5), few (5), kelly (5), coefficients (5), 22974 (5), residual (5), standard (5), lsqrt (5), available (5), 133 (5), just (5), counts (5), know (5), way (5), larger (5), level (5), should (5), every (5), higher (5), run (5), skipped (5), block_r (5), independently (5), may (5), check (5), optimized (5), nshepperd (5), print (5), reds (5), fromintegral (5), games (5), policy (5), strategy (5), simulategame (5), bibliography (4), here (4), require (4), pgo (4), parallelism (4), help (4), complexity (4), 076 (4), coin (4), flip (4), makes (4), doesn (4), further (4), gets (4), bigger (4), looks (4), constant (4), does (4), statistic (4), adjusted (4), degrees (4), freedom (4), median (4), residuals (4), summary (4), 133787000 (4), rbind (4), 133m (4), fit (4), increases (4), fits (4), seems (4), too (4), element_blank (4), strip (4), theme (4), 100000 (4), gwern (4), decision (4), 2022 (4), calculation (4), thus (4), such (4), arithmetic (4), calculations (4), long (4), might (4), after (4), 038 (4), better (4), large (4), also (4), sem_wait (4), workers (4), worker_thread (4), sem_init (4), handle_work_done (4), do_block (4), thread_id (4), get_work (4), arg (4), get_black_val (4), get_red_val (4), pthread_mutex_unlock (4), sem_post (4), pthread_mutex_lock (4), pthread_mutex_t (4), pthread_mutex_initializer (4), sem_t (4), div_round_up (4), stdbool (4), left (4), depend (4), take (4), sem (4), upindex (4), leftindex (4), calc_thread (4), stdlib (4), other (4), them (4), your (4), fourteen (4), retval (4), vector (4), sum (4), zheng (4), playvalue (4), end (4), quit (4), memoise (4), random (4), answer (4), specific (4), walk (4), day (3), javascript (3), given (3), generate (3), slower (3), both (3), 787 (3), near (3), plotting (3), approximations (3), almost (3), negative (3), grows (3), slowly (3), text (3), position (3), 000000 (3), llogsqrt (3), predict (3), llog (3), 100k (3), quite (3), make (3), problem14 (3), compute (3), needs (3), fixed (3), now (3), ever (3), overhead (3), becomes (3), been (3), again (3), provide (3), computed (3), days (3), threadripper (3), minutes (3), original (3), big (3), 400 (3), since (3), runs (3), pthread_create (3), pthread_t (3), solution (3), remaining (3), don (3), need (3), skipping (3), instead (3), col_base (3), row_base (3), descent_task (3), descent (3), right (3), ascent_task (3), soon (3), processes (3), thousands (3), millions (3), vectorize (3), without (3), even (3), total_return (3), iters (3), rand (3), module (3), changing (3), back (3), start (3), set (3), memoization (3), leave (3), class (3), base (3), han (3), statecache (3), simply (3), choices (3), easy (3), 624475549 (3), being (3), sampling (3), replacement (3), solved (3), 296 (3), 322 (3), cell (3), bet (3), solutions (3), brownian (3), interview (3), naive (3), question (3), annotation (2), site (2), hairsp (2), page (2), disabled (2), never (2), close (2), machine (2), isn (2), smart (2), 0m0 (2), user (2), profiling (2), prof (2), fprofile (2), last (2), actually (2), who (2), win (2), bit (2), relative (2), slightly (2), often (2), 573 (2), 563 (2), largest (2), zero (2), well (2), points (2), terms (2), issues (2), somewhere (2), ignoring (2), background (2), geom_point (2), none (2), legend (2), ylab (2), xlab (2), aes (2), geom_line (2), qplot (2), 91897 (2), 978735 (2), 525 (2), 154 (2), etc (2), 0186936 (2), 522088 (2), 22973 (2), 106 (2), 331 (2), things (2), seq (2), net (2), approximating (2), hard (2), course (2), bound (2), guess (2), truncation (2), perhaps (2), sub (2), precision (2), something (2), below (2), ability (2), wasted (2), point (2), scenarios (2), payoffs (2), same (2), computers (2), parallelization (2), range (2), dependencies (2), gpu (2), calculated (2), intermediate (2), speedup (2), skip (2), turns (2), comparing (2), 009 (2), yields (2), arrays (2), presumably (2), around (2), runtime (2), uintptr_t (2), intptr_t (2), meh (2), nasty (2), put (2), asymmetry (2), locking (2), arsed (2), making (2), nice (2), typedef (2), lazy (2), stdint (2), semaphore (2), whole (2), simple (2), most (2), off (2), half (2), looking (2), gives (2), wall (2), breaking (2), evaluated (2), different (2), evaluates (2), many (2), finish (2), efficiency (2), upper (2), worker_task (2), param (2), marker (2), visualization (2), aid (2), synchronization (2), split (2), keep (2), cores (2), spinlock (2), hits (2), constantly (2), own (2), parts (2), his (2), laptop (2), next (2), starts (2), approach (2), diagonalization (2), actual (2), operations (2), modern (2), multi (2), computer (2), far (2), between (2), simplest (2), easiest (2), took (2), write (2), first (2), tops (2), 143 (2), hours (2), milliseconds (2), compiled (2), rather (2), probably (2), avx (2), means (2), instructions (2), ought (2), later (2), pattern (2), factors (2), run_game (2), argv (2), argc (2), fill_array (2), break (2), should_stop (2), rand_lim (2), divisor (2), note (2), was (2), 41984711742427 (2), 15997372030584 (2), requested (2), immediately (2), roots (2), tuple (2), ask (2), length (2), shuffle (2), monte (2), carlo (2), over (2), action (2), decide (2), nothing (2), macro (2), hashmap (2), result (2), string (2), library (2), simulategamelog (2), runif (2), ith (2), sample (2), see (2), quitvalue (2), fact (2), lets (2), choice (2), confirm (2), correct (2), 000000000 (2), returns (2), entire (2), probabilities (2), sequence (2), sound (2), computational (2), analysis (2), shows (2), 3333 (2), 6571 (2), 1667 (2), 1429 (2), 4524 (2), 125 (2), 1111 (2), 841 (2), 048 (2), 09091 (2), 08333 (2), 377 (2), 07692 (2), 202 (2), 3889 (2), 603 (2), 674 (2), 084 (2), 484 (2), 146 (2), 9049 (2), 618 (2), 264 (2), 624 (2), maximum (2), coldwell (2), non (2), corresponds (2), quantitative (2), finance (2), prices (2), stock (2), their (2), bridge (2), counterintuitive (2), rule (2), dollar (2), high (2), efficient (2), implementations (2), adblock, public, service, announcement, quote, send, anonymous, feedback, references, topic, enabled, load, hurt, apparently, sys, 043s, 0m7, 486s, real, 540s, merge, default_, profraw, output, llvm, profdata, dev, trick, sometimes, squeeze, another, did, 03s, compile, reason, replacing, declarations, compiles, _atomic, calculates, omniscient, player, knew, order, expect, howe, 2014, adjusts, drops, multiplier, smaller, offset, converge, numbers, soak, zig, zag, staircase, discretization, sees, 25955e, 00245711, 22048e, 93756e, 2694354, 736, 46229e, 54948e, 10346355, 00010533, 00071383, 00105519, 00453808, 6038, compare, changes, consistent, suspiciously, along, tiny, misfit, term, vanishes, asymptotically, wonder, logarithmic, 294, hidden, erroneous, everywhere, adding, additional, unnecessary, indicate, serious, reveals, wildly, inaccurate, early, hitting, compared, perfectly, ggtitle, 313131, 5b6b6b, 999999, scale_color_manual, dashed, linetype, base_size, theme_bw, color, 11482e, 68411, 91493e, 45612e, 063, 40946e, 66876e, 225, 66931e, 72306e, 917, 34388, 34909, 15215, 34937, 80501, 100m, 5220, 16509, 10b, 52208, 100b, 165098, 080028, 522, 10m, 1650, 28726e, 00187101, 22088e, 45212e, 1512369, 327, 86936e, 70052e, 505, 163, 05298383, 00071444, 00047093, 00121099, 01869362, 185369, 889734, 889729, 19828, 6267169, 0409405, 430, 545, 6454973, 3724555, 286, 62279, 98638, 00526, 96333, 107, 14550, delete, entry, easier, logs, https, doc, statistics, bottomup, values0to22974, txt, read, spend, figure, heuristic, once, falls, represent, number, spent, floating, format, truncating, estimates, avoid, full, rollouts, suspect, turn, calculating, wide, beam, width, through, devoted, increasingly, astronomically, unlikely, contribute, tinier, massive, penalties, lurking, old, network, latency, less, issue, parallelizing, across, useful, cluster, local, done, minimal, control, flow, scream, low, cuda, ensure, stay, gpus, why, shortcut, begin, storing, pre, algorithm, power, caching, short, analytical, expressions, possibilities, october, 184, 78162, finetuned, 32303, 0017, 0146229, 522048, kicks, thought, static, balks, messed, 818, 2m10s, found, closer, bumped, safe, linker, halving, profile, guided, 1000, worse, cuts, lower, skips, computations, doubles, speed, fastest, total, under, 85s, diagonalized, expose, profitable, improves, locality, assigns, nested, within, diagonally, phase, become, setup, moderately, severe, manual, tweaking, suggested, diagram, wise, appears, 075847, ryzen, 1950, 76ya, amd, atomic_store, atomic_load, _mm_pause, col_from, col_to, stdatomic, immintrin, busy, hasn, yet, finishes, computing, necessary, grab, resume, its, computation, little, delay, provides, parallelized, tries, pending, separate, separately, spin, until, moves, 001, reduces, lock, creating, communicating, vastly, greater, addition, division, multiplication, anything, involving, ipc, safely, assumed, cost, equivalent, hundreds, above, worthwhile, difference, programmer, myself, takes, seconds, versions, programmers, advice, however, care, wait, illustrates, potential, ran, substantially, got, 17s, evaluating, due, poor, vectorization, reported, second, 512, fopt, info, vec, 200000, particular, single, depending, previous, cannot, nor, compiler, forfeit, our, despite, reasonably, lots, distant, prior, call, loops, refer, batch, subset, chosen, moving, seem, vmaxp, simd, threaded, traversal, illustration, asymptotic, improved, avg, atoi, srand, shitty, cares, char, rand_max, implemented, fourteen2, show, lambdas, golfed, 624475, 572700, 520043, 466309, 411082, 354246, 295858, 235999, 174761, 112214, 048282, 982391, 913208, 840810, 765412, 687397, 607228, 524702, 434110, 335373, 229437, 119048, 850000, 666667, 500000, fmax, port, 624475548993925, rational, ord, fractional, qualified, ratio, decimal, factor, linear, patient, reasonable, 974, file, least, requesting, bunch, repl, continually, shrinking, tree, structure, follows, sort, wave, ripple, won, revisit, discarded, throw, move, forth, those, understand, sets, logical, dependency, enables, requests, desired, comes, drawback, taking, store, metal, struggle, possibly, tens, gigabytes, memory, 10_000, 10_000_000, typeof, extern, listcomprehension, notes, converted, flat, especially, stops, tracking, tracks, reporting, marginal, free, based, results, confirms, wrote, written, custom, language, ylim, coord_cartesian, facet_wrap, ggplot2, rep, implicit, boundary, trajectories, simulating, fairly, risky, usually, wins, 6243913, 10000000, replicate, mean, 62447555, attain, claimed, specified, two, doing, instantly, worth, 21519192, stack, 295858627, 354246421, 411081973, 466309395, 520043731, 572700079, 840809473, 913207824, 982391061, 048281891, 112213746, 174760756, 235998731, 229437229, 335372960, 434110334, 524701769, 607227911, 687397226, 765411833, 500000000, 666666667, 850000000, 119047619, sapply, balanced, slow, tricky, part, tripped, initially, yielded, accidentally, leaving, dependent, vice, versa, push, towards, middle, hint, remains, were, reversion, always, ride, luck, itself, borrowing, dynamics, recursion, instant, yes, brute, force, optimally, combinatorially, infeasible, illusory, reduce, reused, harder, perfect, example, variables, boundaries, forced, reasoning, opaque, buried, clear, construct, scale, sizes, trades, growing, logarithm, walks, involve, 6667, 343, 444, 067, 5357, 7937, 119, 2857, 9091, 229, 656, 232, 3917, 5606, 7639, 015, 335, 754, 299, 2222, 3455, 4889, 6581, 8618, 114, 434, 356, 3091, 4336, 5779, 7483, 9542, 208, 919, 427, 101, 1818, 2797, 3896, 5152, 6608, 8334, 042, 607, 998, 499, 152, 2555, 3538, 4647, 5916, 7394, 9144, 124, 687, 569, 199, 1538, 2352, 3242, 4234, 5356, 6643, 8143, 9914, 455, 765, 151, 635, 241, 07143, 2179, 2992, 4892, 7338, 886, 065, 276, 531, 223, 696, 026, 06667, 1333, 2029, 2778, 3596, 4504, 5521, 6678, 8006, 9546, 135, 348, 913, 291, 753, 328, 059, 0625, 2593, 3346, 4173, 5092, 6126, 7301, 8648, 417, 982, 355, 811, 378, 094, 05882, 1176, 1785, 2431, 3128, 3888, 4726, 5659, 671, 7903, 9267, 268, 741, 418, 429, 127, 05556, 1684, 2289, 2937, 364, 4409, 5259, 6208, 7275, 8484, 9866, 332, 549, 806, 112, 928, 479, 05263, 1053, 1594, 2163, 2769, 3422, 4133, 4913, 5776, 7823, 045, 206, 393, 612, 869, 175, 541, 986, 528, 1513, 205, 2619, 3229, 4609, 5401, 6278, 7256, 8355, 9598, 102, 265, 453, 673, 931, 236, 601, 041, 574, 219, 006, 04762, 09524, 144, 1948, 2485, 3058, 3674, 4342, 5072, 5876, 6767, 7759, 8874, 013, 157, 511, 732, 659, 095, 249, 027, 04545, 1374, 1856, 2364, 2903, 3481, 4105, 4782, 5523, 6339, 7243, 825, 9381, 066, 211, 568, 049, 354, 716, 661, 284, 051, 04348, 08696, 1313, 1773, 2254, 2764, 3308, 3892, 5211, 5963, 6791, 7708, 873, 9876, 117, 431, 846, 411, 771, 196, 706, 04167, 1258, 1696, 2155, 2638, 3152, 3701, 4292, 4933, 6393, 7233, 8164, 036, 167, 315, 678, 902, 162, 466, 824, 246, 751, 1207, 1626, 2064, 2523, 301, 3528, 4084, 4683, 5332, 6039, 6814, 7667, 861, 9661, 216, 366, 536, 731, 956, 217, 876, 03846, 116, 1562, 198, 2418, 288, 3371, 3895, 4458, 5065, 5723, 6441, 7227, 8091, 011, 415, 587, 783, 927, 03704, 07407, 1117, 1503, 1903, 2322, 2762, 3228, 3724, 4254, 4824, 5439, 6107, 6835, 7632, 8509, 9479, 056, 176, 311, 464, 637, 834, 061, spread, sheet, either, currently, holding, gamble, former, avoidance, doubt, represented, beginning, concludes, 562, 949, 953, 421, 312, 989, 816, 513, 0813295, allocating, covers, guarantees, pick, hit, otherwise, broke, explained, ensemble, strategies, matching, scott, suppose, betting, amount, odds, investment, guarantee, choosing, passively, exposed, slings, arrows, outrageous, fortune, potentially, earn, minimum, artificial, ends, special, process, required, cover, financial, bonds, whose, redemption, share, affected, drives, price, selling, exercising, exercised, trade, money, general, ekström, wanntorp, 2009, american, option, options, pinning, coupon, bond, stas, volkov, fun, construction, throws, loop, neutralize, shouldn, cut, losses, wrong, quitting, knows, coming, chance, exploit, eke, profit, following, pays, fines, want, returned, maximizing, discusses, gambling, 2006, nigel, million, conjecture, 002, change, powerful, improving, shockingly, careful, individual, made, build, providing, verified, these, limiting, treated, stage, about, draws, finite, goal, fluctuated, likely, aspects, importance, certain, certainty, finished, timothy, falcon, asks, drawing, approaches, others, increasing, theory, substack, patreon, blog, support, link, popups, popovers, transclusions, collapsible, sections, tablesorting, image, zooming, enable, sidenotes, website, features, warning, content,
Text of the page (random words):
tex_initializer pthread_mutex_t grab_work_mutex pthread_mutex_initializer define work_queue_len num_blocks work_item_t work_queue work_queue_len pthread_t workers num_threads fp r0_edge num_blocks block_size 1 fp b0_edge num_blocks block_size 1 fp diag_arr num_threads 2 block_size 1 int b_progress num_blocks int r_progress num_blocks work_item_t get_work void sem_wait work_sem pthread_mutex_lock grab_work_mutex work_item_t ret work_queue tail tail if tail work_queue_len tail 0 pthread_mutex_unlock grab_work_mutex return ret meh nasty get put asymmetry with the locking can t be arsed making it nice void put_work work_item_t work work_queue head work head if head work_queue_len head 0 sem_post work_sem void handle_work_done work_item_t work pthread_mutex_lock put_work_mutex b_progress work r work b 1 r_progress work b work r 1 if work r 1 num_blocks b_progress work r 1 work b put_work work_item_t b work b r work r 1 if work b 1 num_blocks r_progress work b 1 work r put_work work_item_t b work b 1 r work r if work b 1 num_blocks work r 1 num_blocks sem_post done_sem pthread_mutex_unlock put_work_mutex int cash int rem_black int rem_red return rem_red rem_black void do_block int thread int block_r int block_b count block_size int base_b 1 block_size block_b int base_r 1 block_size block_r int cur 0 fp cur_dia fp prev_dia for int dia 1 dia count dia cur_dia diag_arr thread cur prev_dia diag_arr thread cur cur cur prev_dia 0 b0_edge base_r dia 1 prev_dia dia r0_edge base_b dia 1 for int ix 0 ix dia ix int b_ix ix int r_ix dia ix 1 int b base_b b_ix int r base_r r_ix fp p fp b fp b r fp value_if_stop cash b r fp value_if_go p prev_dia ix 1 p prev_dia ix 1 cur_dia ix 1 max value_if_stop value_if_go for int dia count 1 dia 0 dia cur_dia diag_arr thread cur prev_dia diag_arr thread cur cur cur r0_edge base_b count dia 1 prev_dia 1 b0_edge base_r count dia 1 prev_dia dia 1 for int ix 0 ix dia ix int b_ix count dia ix int r_ix count 1 ix int b base_b b_ix int r base_r r_ix fp p fp b fp b r fp value_if_stop cash b r fp get_black_val prev_dia ix 1 fp get_red_val prev_dia ix 2 fp value_if_go p get_black_val 1 p get_red_val cur_dia ix 1 max value_if_stop value_if_go r0_edge base_b count 1 cur_dia 1 b0_edge base_r count 1 cur_dia 1 void worker_thread void arg int thread_id intptr_t arg while true work_item_t work get_work do_block thread_id work r work b handle_work_done work return null int main for int i 0 i num_cards i b0_edge i i sem_init work_sem 0 0 sem_init done_sem 0 0 put_work work_item_t r 0 b 0 for int i 0 i num_threads i pthread_create workers i null worker_thread void uintptr_t i sem_wait done_sem printf value g n r0_edge num_cards return 0 this gives a total runtime under clang of 0 85s gcc 1 3s blocks skipping can it be faster of course the fastest code is the code that doesn t run and looking at the work the code does much of it seems to be wasted if you look at the spreadsheet solution the whole bottom left of the spreadsheet is simple if you know you should stop when there are x good cards and y bad cards remaining you don t need to do all the calculations to know you should stop when there x good cards and y bad cards remaining it can only be worse never better this skipping of most of the bottom triangle cuts off almost half the state space because it s the lower triangle and thus skips half the computations and since we are compute bound almost doubles speed include pthread h include stdio h include stdbool h include semaphore h include stdint h num_cards must be a multiple of block_size because i m lazy define num_cards 133787000 define block_size 1000 define num_threads 15 define div_round_up x y x y 1 y define num_blocks div_round_up num_cards block_size define fp double define max x y x y x y define min x y x y x y typedef struct int r int b work_item_t int head int tail sem_t work_sem sem_t done_sem pthread_mutex_t put_work_mutex pthread_mutex_initializer pthread_mutex_t grab_work_mutex pthread_mutex_initializer define work_queue_len num_blocks work_item_t work_queue work_queue_len pthread_t workers num_threads fp r0_edge num_blocks block_size 1 fp b0_edge num_blocks block_size 1 fp diag_arr num_threads 2 block_size 1 int b_progress num_blocks int r_progress num_blocks int skipped num_blocks work_item_t get_work void sem_wait work_sem pthread_mutex_lock grab_work_mutex work_item_t ret work_queue tail tail if tail work_queue_len tail 0 pthread_mutex_unlock grab_work_mutex return ret meh nasty get put asymmetry with the locking can t be arsed making it nice void put_work work_item_t work work_queue head work head if head work_queue_len head 0 sem_post work_sem int cash int rem_black int rem_red return rem_red rem_black void handle_work_done work_item_t work pthread_mutex_lock put_work_mutex b_progress work r work b 1 r_progress work b work r 1 if work b 1 num_blocks work r 1 num_blocks cash work b 1 block_size work r 1 block_size r0_edge work b 1 block_size r_progress work b num_blocks skipped work b 1 work r 1 else if work r 1 num_blocks b_progress work r 1 work b skipped work b put_work work_item_t b work b r work r 1 if work b 1 num_blocks r_progress work b 1 work r put_work work_item_t b work b 1 r work r if work b 1 num_blocks work r 1 num_blocks sem_post done_sem pthread_mutex_unlock put_work_mutex void do_block int thread int block_r int block_b int count block_size int base_b 1 block_size block_b int base_r 1 block_size block_r if skipped block_b skipped block_b block_r for int i 0 i block_size i b0_edge base_r i cash base_b 1 base_r i int cur 0 fp cur_dia fp prev_dia for int dia 1 dia count dia cur_dia diag_arr thread cur prev_dia diag_arr thread cur cur cur prev_dia 0 b0_edge base_r dia 1 prev_dia dia r0_edge base_b dia 1 for int ix 0 ix dia ix int b_ix ix int r_ix dia ix 1 int b base_b b_ix int r base_r r_ix fp p fp b fp b r fp value_if_stop cash b r fp value_if_go p prev_dia ix 1 p prev_dia ix 1 cur_dia ix 1 max value_if_stop value_if_go for int dia count 1 dia 0 dia cur_dia diag_arr thread cur prev_dia diag_arr thread cur cur cur r0_edge base_b count dia 1 prev_dia 1 b0_edge base_r count dia 1 prev_dia dia 1 for int ix 0 ix dia ix int b_ix count dia ix int r_ix count 1 ix int b base_b b_ix int r base_r r_ix fp p fp b fp b r fp value_if_stop cash b r fp get_black_val prev_dia ix 1 fp get_red_val prev_dia ix 2 fp value_if_go p get_black_val 1 p get_red_val cur_dia ix 1 max value_if_stop value_if_go r0_edge base_b count 1 cur_dia 1 b0_edge base_r count 1 cur_dia 1 void worker_thread void arg int thread_id intptr_t arg while true work_item_t work get_work do_block thread_id work r work b handle_work_done work return null int main for int i 0 i num_cards i b0_edge i i sem_init work_sem 0 0 sem_init done_sem 0 0 put_work work_item_t r 0 b 0 for int i 0 i num_threads i pthread_create workers i null worker_thread void uintptr_t i sem_wait done_sem printf value g n r0_edge num_cards return 0 for l 100k this runs in 0 5s not quite halving the runtime profile guided optimization pgo doesn t help 3 for kicks i thought i d calculate the largest l possible this turns out to be l 133 787 000 higher values require static arrays so large that the linker balks presumably there s a way around that but 133m seems big enough i messed with the block size some more on l 2m 818 1 2m10s and found that a block size closer to 1 000 seems better than 400 so for a 133m run i bumped it to 1 000 to be safe since as the card count gets bigger the optimal block size presumably also slowly gets bigger after 9 days on my threadripper 8 17 october 2022 51 cpu core days 184 331 cpu core minutes the exact value of l 133 787 000 turns out to be 6 038 22 comparing this to my original square root approximation of 0 0186936 0 522088 sqrt 133787000 6 038 78162 the approximation has an error of 0 009 if we include that into the square root approximation the finetuned approximation then yields 0 0146229 0 522048 sqrt 133787000 6 038 32303 which has a better error of 0 0017 faster where could one go from the final block skip version short of analytical expressions or approximations a few possibilities exact calculation caching begin storing pre computed values in the algorithm such as every power of 10 after all now that values like l 133m have been calculated why should they ever be calculated again they provide a shortcut to all intermediate values and a speedup for larger values gpus small local arithmetic calculations done in parallel with minimal control flow or long range dependencies scream for a gpu implementation might require low level cuda programming to ensure that the calculations stay in the gpu thread they should cluster parallelization for larger problems network overhead latency becomes less of an issue and parallelizing across multiple computers becomes useful approximation ε probability truncation as the card count increases more of the state space is devoted to increasingly astronomically unlikely scenarios which contribute ever tinier values to the final value of the game because there are no massive payoffs or penalties lurking only the same old 1 thus one could truncating value estimates at some small fixed value ε to avoid full rollouts i suspect that such an approximation would turn it into 𝒪 1 space 𝒪 l time because one is now just calculating a wide diagonal beam of fixed width down through the square of all possible states ε value truncation perhaps sub machine precision the exact calculation is not exact here once something falls below double precision floating point format s ability to represent a number so compute spent on that is wasted it is hard to know if the value ε before you spend the compute of course so one needs to figure out a way to bound it or have a good heuristic to guess it approximating values read table https gwern net doc statistics decision 2022 10 03 feepingcreature problem14 bottomup values0to22974 txt df rbind data frame cards seq 0 22974 value values v1 type exact data frame cards c 100000 value 165 076 type exact df df 1 delete 0 card entry to make things easier with the logs llog lm value log cards data df summary llog residuals min 1q median 3q max 6 62279 4 98638 1 00526 3 96333 107 14550 coefficients estimate std error t value pr t intercept 106 6454973 0 3724555 286 331 2 22e 16 log cards 17 6267169 0 0409405 430 545 2 22e 16 residual standard error 6 19828 on 22973 degrees of freedom multiple r squared 0 889734 adjusted r squared 0 889729 f statistic 185369 on 1 and 22973 df p value 2 22e 16 lsqrt lm value sqrt cards data df summary lsqrt residuals min 1q median 3q max 0 05298383 0 00071444 0 00047093 0 00121099 0 01869362 coefficients estimate std error t value pr t intercept 1 86936e 02 3 70052e 05 505 163 2 22e 16 sqrt cards 5 22088e 01 3 45212e 07 1512369 327 2 22e 16 residual standard error 0 00187101 on 22974 degrees of freedom multiple r squared 1 adjusted r squared 1 f statistic 2 28726e 12 on 1 and 22974 df p value 2 22e 16 the fit v 0 0186936 0 522088 cards so 100k 165 080028 not quite 165 076 1m 522 0 10m 1650 96 100m 5220 86 1b 16509 85 10b 52208 78 100b 165098 70 etc llogsqrt lm value log cards sqrt cards data df summary llogsqrt residuals min 1q median 3q max 80 34388 1 34909 0 15215 1 34937 26 80501 coefficients estimate std error t value pr t intercept 2 66931e 01 1 72306e 01 154 917 2 22e 16 log cards 4 40946e 00 2 66876e 02 165 225 2 22e 16 sqrt cards 3 91493e 01 7 45612e 04 525 063 2 22e 16 residual standard error 2 68411 on 91897 degrees of freedom multiple r squared 0 978735 adjusted r squared 0 978735 f statistic 2 11482e 06 on 2 and 91897 df p value 2 22e 16 df rbind df data frame cards df cards value predict llog type log data frame cards df cards value predict lsqrt type data frame cards df cards value predict llogsqrt type log p qplot x cards y value color type data df theme_bw base_size 50 p geom_line aes x cards y value linetype dashed size 5 scale_color_manual values c 999999 5b6b6b 313131 000000 xlab card draw ylab winnings theme legend position none ggtitle vs log approximation of problem 14 value geom_point size 8 theme strip background element_blank strip text x element_blank the square root fits well enough that adding additional terms seems unnecessary while the residual values indicate that the log fit has some serious issues somewhere plotting reveals that the log is wildly inaccurate early on hitting negative values ignoring that it grows too slowly compared to the true value while the square root fits perfectly plotting the square root logarithmic approximations for the problem 14 value of card counts 1 22 294 100 000 the square root fits so well that the exact points are hidden while the log is erroneous almost everywhere the square root fit looks suspiciously like it is just the initial expected value of 1 card 0 5 along with a tiny near zero misfit term that vanishes as the card value asymptotically increases i wonder if the limit is just 0 5 l the largest available exact value l 133m changes the approximation consistent with that compare with the final available exact value of 𝑙 133 787 000 df rbind df data frame cards c 133787000 value 6038 22 type exact lsqrt lm value sqrt cards data df summary lsqrt residuals min 1q median 3q max 0 10346355 0 00010533 0 00071383 0 00105519 0 00453808 coefficients estimate std error t value pr t intercept 1 46229e 02 2 54948e 05 573 563 2 22e 16 sqrt cards 5 22048e 01 1 93756e 07 2694354 736 2 22e 16 residual standard error 0 00245711 on 22974 degrees of freedom multiple r squared 1 adjusted r squared 1 f statistic 7 25955e 12 on 1 and 22974 df p value 2 22e 16 it adjusts the coefficients a bit and then the relative error drops the 0 5 multiplier gets slightly smaller but the offset intercept gets slightly bigger so it looks like it does converge to 0 5 l with for small numbers an intercept as a constant to help soak up the zig zag staircase discretization one often sees in probability problems howe 2014 further calculates that an omniscient player who knew the deck order could expect to win 4 04 ︎ it doesn t compile as is with clang for some reason replacing the volatile bool declarations with _atomic bool compiles but is 0 1s slower for both gcc clang 2 9s 3s ︎ as a last optimization trick can sometimes squeeze out another few of performance like it did with kelly coin flip but in this case clang pgo actually makes it slower by 0 03s clang ofast march native pthread o khoth lm khoth c fprofile generate khoth dev null llvm profdata merge default_ profraw output profiling prof clang ofast march native pthread o khoth lm khoth c fprofile use profiling prof time khoth value 165 076 real 0m0 540s user 0m7 486s sys 0m0 043s while one would think pgo would never hurt we apparently are so close to the machine optimal performance by parallelism that pgo isn t smart enough to help given the complexity ︎ error javascript disabled backlinks similar links and the bibliography require js enabled to load backli...
|
