Inside Bitcoin

Opening the selected file…

₿MyBitcoinExplorer

Bitcoin, in focus.
Explore the network. Understand the connections.

Explore Bitcoin with clarity.

READ THE CODE

Inside Bitcoin

The code behind the network, with room to understand it.

Stable release v32.1bitcoin/bitcoin · f0de87f04062 ↗3,020 source files · 47.5 MB stored on the server340 file guides

Release published 2026-10-28 · Snapshot fetched 2026-11-01. Latest stable release at fetch time; development branches and Git history are excluded. Only the selected code window and visible folders load here.

bitcoin / bitcoinstable

Find a file

▤ gen_basefpbits.sage

▤ gen_params.sage

▤ log2_factorial.sage

▤ arith_uint256.hGuide

▤ bitcoin-chainstate.cpp

▤ bitcoin-cli-res.rc

▤ bitcoin-cli.cppGuide

▤ bitcoin-res.rc

▤ bitcoin-tx-res.rc

▤ bitcoin-tx.cpp

▤ bitcoin-util-res.rc

▤ bitcoin-util.cpp

▤ bitcoin-wallet-res.rc

▤ blockencodings.cppGuide

▤ blockencodings.hGuide

▤ blockfilter.cppGuide

▤ blockfilter.hGuide

▤ chain.cppGuide

▤ chain.h

▤ chainparams.cppGuide

▤ chainparams.h

▤ chainparamsbase.cppGuide

▤ chainparamsbase.hGuide

▤ chainparamsseeds.h

▤ checkqueue.hGuide

▤ clientversion.cpp

▤ clientversion.hGuide

▤ cluster_linearize.h

▤ CMakeLists.txt

▤ coins.cppGuide

▤ coins.hGuide

▤ compressor.cppGuide

▤ deploymentstatus.cpp

▤ deploymentstatus.h

▤ dummywallet.cpp

▤ external_signer.cpp

▤ merkleblock.cppGuide

▤ merkleblock.hGuide

▤ musig.cpp

▤ musig.h

▤ net_permissions.cppGuide

▤ net_permissions.h

▤ net_processing.cppGuide

▤ netaddress.cppGuide

▤ private_broadcast.cpp

▤ private_broadcast.h

▤ threadsafety.hGuide

▤ tinyformat.h

▤ torcontrol.cppGuide

▤ validation.cppGuide

▤ validation.h

▤ validationinterface.cpp

▤ validationinterface.h

▤ versionbits_impl.h

▤ versionbits.cpp

▤ versionbits.h

▤ walletinitinterface.h

▤ CMakeLists.txtGuide

▤ libbitcoinkernel.pc.in

bitcoin / src / minisketch / doc / log2_factorial.sage

Download source ↓

2,596 bytes · SHA-256 b3b699ddb176b12d… · View upstream ↗

1import bisect
2
3INPUT_BITS = 32
4TABLE_BITS = 5
5INT_BITS = 64
6EXACT_FPBITS = 256
7
8F = RealField(100) # overkill
9
10def BestOverApproxInvLog2(mulof, maxd):
11    """
12    Compute denominator of an approximation of 1/log(2).
13
14    Specifically, find the value of d (<= maxd, and a multiple of mulof)
15    such that ceil(d/log(2))/d is the best approximation of 1/log(2).
16    """
17    dist=1
18    best=0
19    # Precomputed denominators that lead to good approximations of 1/log(2)
20    for d in [1, 2, 9, 70, 131, 192, 445, 1588, 4319, 11369, 18419, 25469, 287209, 836158, 3057423, 8336111, 21950910, 35565709, 49180508, 161156323, 273132138, 385107953, 882191721]:
21        kd = lcm(mulof, d)
22        if kd <= maxd:
23            n = ceil(kd / log(2))
24            dis = F((n / kd) - 1 / log(2))
25            if dis < dist:
26                dist = dis
27                best = kd
28    return best
29
30
31LOG2_TABLE = []
32A = 0
33B = 0
34C = 0
35D = 0
36K = 0
37
38def Setup(k):
39    global LOG2_TABLE, A, B, C, D, K
40    K = k
41    LOG2_TABLE = []
42    for i in range(2 ** TABLE_BITS):
43        LOG2_TABLE.append(int(floor(F(K * log(1 + i / 2**TABLE_BITS, 2)))))
44
45    # Maximum for (2*x+1)*LogK2(x)
46    max_T = (2^(INPUT_BITS + 1) - 1) * (INPUT_BITS*K - 1)
47    # Maximum for A
48    max_A = (2^INT_BITS - 1) // max_T
49    D = BestOverApproxInvLog2(2 * K, max_A * 2 * K)
50    A = D // (2 * K)
51    B = int(ceil(F(D/log(2))))
52    C = int(floor(F(D*log(2*pi,2)/2)))
53
54def LogK2(n):
55    assert(n >= 1 and n < (1 << INPUT_BITS))
56    bits = Integer(n).nbits()
57    return K * (bits - 1) + LOG2_TABLE[((n << (INPUT_BITS - bits)) >> (INPUT_BITS - TABLE_BITS - 1)) - 2**TABLE_BITS]
58
59def Log2Fact(n):
60    # Use formula (A*(2*x+1)*LogK2(x) - B*x + C) / D
61    return (A*(2*n+1)*LogK2(n) - B*n + C) // D + (n < 3)
62
63RES = [int(F(log(factorial(i),2))) for i in range(EXACT_FPBITS * 10)]
64
65best_worst_ratio = 0
66
67for K in range(1, 10000):
68    Setup(K)
69    assert(LogK2(1) == 0)
70    assert(LogK2(2) == K)
71    assert(LogK2(4) == 2 * K)
72    good = True
73    worst_ratio = 1
74    for i in range(1, EXACT_FPBITS * 10):
75        exact = RES[i]
76        approx = Log2Fact(i)
77        if not (approx <= exact and ((approx == exact) or (approx >= EXACT_FPBITS and exact >= EXACT_FPBITS))):
78            good = False
79            break
80        if worst_ratio * exact > approx:
81            worst_ratio = approx / exact
82    if good and worst_ratio > best_worst_ratio:
83        best_worst_ratio = worst_ratio
84        print("Formula: (%i*(2*x+1)*floor(%i*log2(x)) - %i*x + %i) / %i; log(max_ratio)=%f" % (A, K, B, C, D, RR(-log(worst_ratio))))
85        print("LOG2K_TABLE: %r" % LOG2_TABLE)
86

A READING COMPANION

Source available. Guide coming next.

This file is included in the stable source snapshot. A file-specific guide has not been published yet.

340 guided files · 2,680 pending. Guides cover key sections, not every line.

cmake/bitcoin-build-config.h.in src/consensus/amount.h src/consensus/consensus.h src/primitives/block.h src/primitives/transaction.h src/crypto/sha256.h src/util/moneystr.h src/clientversion.h src/uint256.h src/script/script.h src/policy/policy.h CMakeLists.txt README.md COPYING src/consensus/tx_check.cpp src/consensus/tx_verify.cpp src/consensus/merkle.cpp src/pow.cpp src/validation.cpp src/script/interpreter.cpp src/script/solver.cpp src/script/sign.cpp src/key_io.cpp src/net.cpp src/net_processing.cpp src/netaddress.cpp src/protocol.h src/wallet/wallet.cpp src/wallet/spend.cpp

Code page 1

src/wallet/receive.cpp

src/wallet/coinselection.cpp

src/consensus/validation.h

src/primitives/transaction.cpp

src/script/descriptor.cpp

src/bitcoin-cli.cpp

src/rpc/blockchain.cpp

src/rpc/rawtransaction.cpp

src/init.cpp

src/crypto/sha256.cpp

src/consensus/merkle.h

src/consensus/tx_check.h

src/consensus/tx_verify.h

src/policy/feerate.h

src/policy/feerate.cpp

src/primitives/transaction_identifier.h

src/chainparamsbase.h

src/chainparamsbase.cpp

src/util/moneystr.cpp

src/crypto/ripemd160.h

src/crypto/sha1.h

src/crypto/sha512.h

src/crypto/hmac_sha256.h

src/crypto/hmac_sha512.h

src/crypto/hmac_sha256.cpp

src/crypto/hmac_sha512.cpp

src/crypto/hkdf_sha256_32.h

src/crypto/hkdf_sha256_32.cpp

src/support/cleanse.h

src/support/cleanse.cpp

src/crypto/siphash.cpp

src/crypto/muhash.h

src/crypto/chacha20.h

src/crypto/poly1305.h

src/crypto/chacha20poly1305.h

src/crypto/chacha20poly1305.cpp

src/util/chaintype.cpp

src/util/obfuscation.h

src/util/byte_units.h

src/util/overflow.h

src/blockencodings.cpp

src/net_permissions.cpp

src/policy/packages.cpp

src/policy/rbf.cpp

src/policy/truc_policy.cpp

src/policy/ephemeral_policy.cpp

src/policy/settings.cpp

src/policy/policy.cpp

src/node/transaction.cpp

src/node/coin.cpp

src/rpc/client.cpp

src/rpc/external_signer.cpp

src/rpc/request.cpp

src/rpc/server_util.cpp

src/rpc/fees.cpp

src/rpc/output_script.cpp

src/rpc/rawtransaction_util.cpp

src/rpc/rawtransaction_util.h

src/rpc/register.h

src/rpc/request.h

src/rpc/server_util.h

src/rpc/protocol.h

src/rpc/server.h

src/rpc/signmessage.cpp

src/rpc/txoutproof.cpp

src/rpc/util.cpp

src/rpc/util.h

src/wallet/rpc/addresses.cpp

src/wallet/rpc/backup.cpp

src/wallet/rpc/coins.cpp

src/wallet/rpc/encrypt.cpp

src/wallet/rpc/signmessage.cpp

src/wallet/rpc/util.cpp

src/wallet/rpc/util.h

src/wallet/coincontrol.cpp

src/wallet/coincontrol.h

src/wallet/context.cpp

src/wallet/context.h

src/wallet/crypter.cpp

src/wallet/crypter.h

src/wallet/db.cpp

src/wallet/export.cpp

src/wallet/external_signer_scriptpubkeyman.cpp

src/wallet/rpc/spend.cpp

src/wallet/rpc/transactions.cpp

src/wallet/rpc/wallet.cpp

src/wallet/feebumper.cpp

src/wallet/feebumper.h

src/index/base.h

src/index/base.cpp

src/index/txindex.h

src/index/txindex.cpp

src/index/txindex_key.h

src/index/txospenderindex.h

src/index/txospenderindex.cpp

src/index/blockfilterindex.h

src/index/blockfilterindex.cpp

src/index/coinstatsindex.h

src/index/coinstatsindex.cpp

src/index/db_key.h

src/index/disktxpos.h

src/kernel/chain.cpp

src/kernel/chain.h

src/kernel/checks.cpp

src/kernel/checks.h

src/kernel/context.cpp

src/kernel/context.h

src/kernel/cs_main.cpp

src/kernel/cs_main.h

src/kernel/disconnected_transactions.cpp

src/kernel/disconnected_transactions.h

src/kernel/mempool_removal_reason.cpp

src/kernel/mempool_removal_reason.h

src/kernel/coinstats.cpp

src/kernel/coinstats.h

src/kernel/chainparams.cpp

src/kernel/chainparams.h

src/wallet/sqlite.cpp

src/wallet/sqlite.h

src/wallet/transaction.cpp

src/wallet/transaction.h

src/wallet/dump.cpp

src/wallet/dump.h

src/wallet/init.cpp

src/wallet/walletutil.cpp

src/wallet/walletutil.h

src/wallet/wallettool.cpp

src/wallet/wallettool.h

src/wallet/export.h

src/wallet/migrate.cpp

src/wallet/migrate.h

src/wallet/db.h

src/wallet/walletdb.cpp

src/wallet/interfaces.cpp

src/wallet/scriptpubkeyman.cpp

src/wallet/scriptpubkeyman.h

src/kernel/bitcoinkernel.cpp

src/kernel/bitcoinkernel.h

src/kernel/bitcoinkernel_wrapper.h

src/node/chainstate.cpp

src/node/chainstate.h

src/node/blockstorage.cpp

src/node/blockstorage.h

src/node/mempool_persist.cpp

src/node/mempool_persist.h

src/node/utxo_snapshot.cpp

src/node/utxo_snapshot.h

src/node/kernel_notifications.cpp

src/node/kernel_notifications.h

src/node/blockmanager_args.cpp

src/kernel/blockmanager_opts.h

src/util/expected.cpp

src/policy/settings.h

src/util/types.h

src/kernel/messagestartchars.h

src/kernel/warning.h

src/util/exception.h

src/common/license_info.h

src/node/coins_view_args.h

src/node/database_args.h

src/util/batchpriority.h

src/util/ui_change_type.h

src/node/coins_view_args.cpp

src/node/peerman_args.h

src/util/serfloat.h

src/node/blockmanager_args.h

src/node/database_args.cpp

src/util/overloaded.h

src/interfaces/types.h

src/node/chainstatemanager_args.h

src/node/minisketchwrapper.h

src/util/macros.h

src/util/syserror.h

src/common/run_command.h

src/util/bytevectorhash.cpp

src/node/mempool_persist_args.cpp

src/util/exec.h

src/util/rbf.h

src/crypto/hex_base.h

src/node/mempool_persist_args.h

src/interfaces/echo.h

src/util/any.h

src/util/batchpriority.cpp

src/util/threadnames.h

src/node/coin.h

src/node/mempool_args.h

src/util/asmap.h

src/util/bytevectorhash.h

src/node/context.cpp

src/util/insert.h

src/util/readwritefile.h

src/node/peerman_args.cpp

src/node/interface_ui.cpp

src/interfaces/handler.h

src/node/mining_args.h

src/util/hasher.cpp

src/common/init.h

src/kernel/mempool_limits.h

src/common/system.h

src/crypto/sha3.h

src/util/threadinterrupt.cpp

src/node/protocol_version.h

src/util/exception.cpp

src/common/messages.h

src/node/connection_types.cpp

src/util/bip32.h

src/common/license_info.cpp

src/util/stdmutex.h

src/common/run_command.cpp

src/util/check.cpp

src/util/golombrice.h

src/node/types.h

src/node/timeoffsets.h

src/util/readwritefile.cpp

src/util/fastrange.h

src/util/signalinterrupt.h

src/util/task_runner.h

src/util/syserror.cpp

src/common/interfaces.cpp

src/common/types.h

src/util/threadinterrupt.h

src/kernel/chainstatemanager_opts.h

src/node/psbt.h

src/policy/ephemeral_policy.h

src/util/trace.h

src/common/url.cpp

src/kernel/mempool_options.h

src/util/serfloat.cpp

src/kernel/notifications_interface.h

src/node/timeoffsets.cpp

src/node/warnings.cpp

src/util/hash_type.h

src/crypto/hex_base.cpp

src/node/eviction.h

src/util/tokenbucket.h

src/crypto/aes.h

src/common/pcp.h

src/util/feefrac.cpp

src/node/transaction.h

src/util/threadnames.cpp

src/common/signmessage.h

src/util/exec.cpp

src/util/signalinterrupt.cpp

Independent explanations by MyBitcoinExplorer. Not affiliated with or endorsed by Bitcoin Core. Guides are educational and do not replace the source or its tests.

Bitcoin Core source © its contributors, distributed under the MIT license. Original notices and bundled third-party licenses are retained in the source tree.