What is the exact formula for calculating transaction fees? According to the Wiki:


  If the blocksize is more than 250 kB, transactions get increasingly more expensive as the blocksize approaches the limit of 500 kB. Sending a transaction when the blocksize is 400 kB will cost 5 times the normal amount; sending when it's 499 kB will cost 500x, etc.


What is the exact formula that determines the transaction fee?
See GetMinFee() in main.h for the code which determines the minimum transaction fee.

The part you're describing is implemented as follows:

// Raise the price as the block approaches full
if (nBlockSize != 1 &amp;&amp; nNewBlockSize &gt;= MAX_BLOCK_SIZE_GEN/2)
{
    if (nNewBlockSize &gt;= MAX_BLOCK_SIZE_GEN)
        return MAX_MONEY;
    nMinFee *= MAX_BLOCK_SIZE_GEN / (MAX_BLOCK_SIZE_GEN - nNewBlockSize);
}


where:


nBlockSize depends on who we are:

if we're a user making a new transaction, nBlockSize is 1
if we're a node deciding whether to relay an incoming transaction, nBlockSize is 1000
if we're a miner deciding which transactions to include in a new block, nBlockSize is the size of the block we're building before adding the new transaction

nNewBlockSize is the size of the block including the new transaction
MAX_BLOCK_SIZE_GEN is 500kB
MAX_MONEY is 21 million BTC (all the money in the world)


so it's saying:


if we're either deciding whether to relay or mine the transaction, and adding the transaction would make the block over 50% full:

never allow a transaction that makes the block 100% full
otherwise scale the fee up by a factor of 500kB / (500kB - nNewBlockSize)



Note: by rearranging the symbols, we get exactly what Meni wrote in his answer:

Fee = Normal fee / ((500kB - size) / 500kB)
         = Normal fee / (1 - size / 500kB)