Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Social Engineering: Theory and Practice
- PO8 <bart@cs.uoregon.edu>
- March 23, 1997
- The Netrunner runner Prep card Social Engineering is an oft-used
- card: it provides both an early-game speedup and a way of
- dealing with particularly nasty ice in the late game. It,
- along with its early-game counterpart Inside Job, is an
- important runner-deck tool. However, Social Engineering
- suffers somewhat from a bad reputation. It is all too easy for
- the runner to lose more bits than they can afford at a critical
- time during the game. And yet, if the Runner risks too few
- bits, the chances of success are not very high.
- The inventors of the branch of Mathematics known as Game Theory
- wanted to answering these very sorts of economic questions.
- Game Theory can tell us exactly how to play Social Engineering
- optimally in a given situation. In this article, I will
- describe these optimal strategies for Social Engineering, and
- give some suggestions about how to convert this theory into
- practice.
- Here's the rules for Social Engineering, as taken from
- BitByte's (<adriant@greenie.com>) spoiler list
- (http://home.pacific.net.sg/~bitbyte).
- Social Engineering: Prep (1) [1.0 U]
- Hide at least (2) from your pool in your hand; the Corp
- then guesses how many bits you hid. If the Corp guesses
- correctly, lose that many bits. Otherwise, choose a
- data fort and a piece of ICE on that fort. Then make a
- run on that fort, during which you automatically pass
- that piece of ICE.
- Assume a pool of n bits. Then, let us choose to risk i bits
- [2 <= i <= n] with probability proportional to 1/i. We must
- normalize, so we are chosing to risk i bits with probability
- p(i) = (1/i) / (1/2 + 1/3 + ... + 1/n)
- Thus, when n = 5, we have probabilities
- i p(i)
- 2 0.39
- 3 0.26
- 4 0.19
- 5 0.15
- Now imagine that the corp chooses any pure strategy (i.e., it
- always guesses some particular number of bits). Its expected
- return on this strategy (i.e., the number of bits it expects to
- cost the runner due to guessing correctly) is identical.
- i e(i)
- 2 0.78
- 3 0.78
- 4 0.78
- 5 0.78
- In other words, no matter what pure strategy the corp picks, it
- will cost the runner 1.78 bits, on average, to play social
- engineering. It can be proven from this that any combination of
- pure corp strategies will achieve the same result, and thus
- this strategy is optimal for the runner (although the proof
- is outside the scope of this paper).
- Unfortunately, the above "optimal" strategy is based on a
- fairly unrealistic assumption. Presumably the runner
- is playing this card because they will receive some utility
- from a successful run, not just to avoid losing bits.
- Unfortunately, there is no clear "value of being able to pass a
- selected piece of ice" in the game. Let us arbitrarily set
- this value at 3 bits, just to see how it affects our
- calculations. (Why 3 bits? Inside Job, which costs 2 bits,
- will let us pass the 1st piece of ice for free. Let us assume
- that the value of passing an arbitrary piece of ice is half
- again as much. We will generalize later in any case.)
- We will now use a different strategy, namely; we will risk i
- bits with probability 1/i+3. Normalizing gives us
- p(i) = (1/(i+3)) / (1/5 + 1/6 + ... + 1/(n+3))
- When n = 5, we choose with probability
- i p(i)
- 2 0.32
- 3 0.26
- 4 0.23
- 5 0.20
- and the corp's expected return for their pure strategy
- (including the three bit benefit of preventing the run
- as well as the cost to the runner of being guessed and of
- playing the card) is
- i e(i)
- 2 2.6
- 3 2.6
- 4 2.6
- 5 2.6
- Thus, we have an optimal strategy for the runner under the new
- conditions, under which it will cost the runner about 2.6 bits,
- including the opportunity cost of missed runs, to play Inside
- Job. (There is some additional opportunity cost of playing a
- Prep during the run, but this is difficult to estimate and
- probably reasonably small in any case.) Note how much the
- probabilities have flattened out. Indeed, as the value to the
- corp of an unsuccessful run gets large, it swamps the expected
- value of making the runner lose the guess bits, and the
- runner's optimal strategy quickly converges on simply picking a
- random value uniformly from the range 2..n .
- A natural question to ask about strategy involves asymptotic
- behavior: what is the optimal strategy as the size of the
- runner's bit pool n gets large?
- limit n->inf sum(i=2..n, 1/i)
- diverges, so the more bits the runner has, the better off they
- are. Notice that the expected return for the corp as a function
- of the runner's bit pool size n is
- e(n) = 1 + 1/(1/5 + 1/6 + ... + 1/(n+3))
- Obviously, the expected corp return converges on 1. But don't
- be fooled: the divergence of this "harmonic series" is notoriously
- slow. When n = 100 (surely infinity from most corps' point
- of view) we still have e(n)=1.32 .
- Note that we picked a utility of 3 for a successful run fairly
- arbitrarily. Depending on the game situation, this utility
- estimate could be wildly off. E.g., you know there's a
- Political Overthrow in a fort, and it's protected by
- Filter-Filter-Colonel Failure. Your icebreakers are Codecracker
- and Raptor. How much would you be willing to pay for a
- Social? On the other hand, a Filter protects a Holovid
- Campaign, but you don't have any icebreakers yet. How much
- would you be willing to pay for a Social?
- Fortunately, the calculations we have been performing
- generalize quite easily to the case of a u-bit utility:
- p(i,n,u) = (1/(i+u)) / (1/(2+u) + 1/(3+u) + ... + 1/(n+u))
- e(n,u) = 1 + 1/(1/(2+u) + 1/(3+u) + ... + 1/(n+u))
- One interesting way to pick the utility is to ask the card itself
- how much it values a run at! We do this by noting that the
- card is presumably zero-sum, and thus when e(n,u) = u presumably
- the corp expects to cost the runner exactly the amount that the
- runner expects to benefit from the run. Thus we need to solve
- 1 + 1/(1/(2+u) + 1/(3+u) + ... + 1/(n+u)) = u
- i.e.
- (1/(2+u) + 1/(3+u) + ... + 1/(n+u)) = 1/(u-1)
- for u. I don't see how to do this analytically, but numerically,
- we find the following:
- n u
- 2 *
- 3 4.5
- 4 3.0
- 5 2.4
- 6 2.1
- 7 2.0
- 8 1.9
- 9 1.8
- 10 1.8
- ...
- 100 1.3
- The * at n = 2 is because the equation for u is singular
- at this value, and thus no solution exists. Intuitively, this
- is because the corp will never guess wrong in this case, and so
- the runner is stupid to play the card! The fact that the u
- value is dependent on the size n of the runner bit pool is
- rather strange, but points up the fact that as the runner has
- more bits, his chances of using this card successfully just get
- better and better, and so a run made using the card is worth
- less and less.
- Note that once the runner has 6 or more bits, the expected
- return when playing optimally (at u=3) doesn't change much as
- the bit pool increases. However, what does change is the risk
- of a disastrous outcome for the runner. It is true that the
- expected return for the corp if it always chooses n is exactly
- the same as if it always chooses 2. However, in the first
- case, if the corp guesses right, the runner loses all their
- bits. This will happen very rarely, but the runner may be
- risk-averse; willing to lose more on average to avoid the risk
- of major losses. Fortunately, limiting risk in this framework
- is easily accomplished: the runner can treat the pool as though
- it has only as many bits as the runner is willing to risk, and
- calculate accordingly. Again, the cost of this risk management
- becomes very high at 4 bits or below, and I don't advise it ---
- if losing 4 bits would be a disaster for the runner, the runner
- shouldn't be playing a Social Engineering at that point.
- A final question is how to use our formulae in a game situation.
- If one is playing online, it's relatively straightforward to
- have a "Social Engineering bit picker" sitting in a window on
- one's terminal, which will select bit value b(n,u) from the
- appropriate probability distribution p(i,n,u). If one is
- playing head-to-head, it is possible to program a programmable
- calculator, PDA, etc., to perform this same calculation.
- Unfortunately, this may or may not be allowed by a tournament
- director, and it may be cumbersome and unpleasant in any case.
- Lacking a programmable calculator or PDA, the runner could use
- a set of tables for d100, parameterized by n and u, to select
- bit values. These tables are included as Appendix A to this
- article. In fact, since it is highly desirable to screen the
- die roll used for this selection from the runner, a very
- reasonable approach is to glue the tables to the inside of a
- cardboard screen, behind which the dice are rolled and the bits
- selected.
- What is really desired is an approximation or set of
- approximations using just ordinary die rolls and no difficult
- arithmetic, such that a selection reasonable approximating
- optimality can be quickly and unobtrusively carried out in a
- game situation. Unfortunately, I see no obvious rules of thumb
- for small n and/or u. For u >= 4 and n >= 5, however, it
- appears that the error induced by merely rolling a die and
- guessing as many bits as it says (rerolling if it is out of
- range) is fairly small. We can quantify the cost of this
- non-optimal strategy. The expected return for the corp is
- c(i) = (1 + i + u) * (1/(n-1) - p(i))
- where p(i) is the true probability that should be assigned to
- the i-th bit. It is clear that the corp's best bet is always
- to take i=n, and that the largest error obtains when u=4. It
- turns out that the error gets larger as n increases (which
- makes intuitive sense, since the runner is supposed to be
- getting a better and better deal, and isn't) but stays
- very close to 1/2 bit for a wide range of n and u values
- above n >= 5 and u >= 4. This is another interesting consequence
- of the slow divergence of the harmonic series --- we know that
- the error becomes infinite for large enough n, but when n=100,
- we still have error less than 0.72!
- One unfortunate effect of this strategy, however, is that the
- optimal corp strategy is to guess the entire value of the bit
- pool. This might make a risk-averse runner very nervous,
- especially since this corp strategy gets slightly better as the
- size of the runner bit pool increases. An obvious way to
- counter this problem is to count die rolls of 1 as 2s: this
- overweights the value 2 at the expense of the other values. It
- turns out that the optimal corp strategy (again for n >= 5 and
- u >=4) is now to always guess 2. Fortunately, the expected
- corp gain over optimal strategy is still about 1/2 bit, and
- falls rapidly off as n increases (for fixed u).
- All of the above is pretty abstract. Here's what I suggest
- as a runner strategy for Social Engineering, given that neither
- software nor tables are available:
- (1) Figure out how much the run is worth. Call this
- number u. If u is less than 3 bits, don't play the
- Social.
- (2) Figure out how many bits the pool will have after
- playing the social. Call this number n.
- (3) If n is more bits that the runner can safely lose,
- reduce n to the number of bits the runner can safely lose.
- (4) If n is 4 or less and u < 5, don't play the Social.
- (5) If n is greater than 6:
- (5a) Obtain or synthesize an m-sided die,
- with n > m.
- (5b) Reroll until the result r of the roll
- satisfies 1 <= r <= n.
- (5c) If r is 1, make r be two.
- (5d) Risk r bits.
- (6) Otherwise:
- (6b) Obtain a 6-sided die.
- (6c) Reroll until the result r of the roll
- satisfies 2 <= r <= n.
- (6d) Risk r bits.
- When written out like this, the algorithm looks pretty complicated.
- In point of fact, it's pretty straightforward once you get the hang
- of it.
- One last obvious question is: what of the poor Corp? Well,
- the Runner has been careful to make any strategy yield
- pretty similar results. The Corp must simply pick randomly
- among the available strategies, in order to prevent the Runner
- guessing what's going to happen. Here's the algorithm I suggest
- for the Corp.
- (1) Figure out how many bits the pool will have after
- playing the social. Call this number n.
- (2) Figure out how many bits the runner can safely lose.
- If this is less than n, set n to this value + 1.
- (3) If the runner is playing with a table or device,
- use a die to select randomly from the range 2..n.
- (4) If n > 6, roll an m-sided die, and count any 1 result
- as a n, until the result r is in range. Guess r.
- (5) If n <= 6, roll a 6-sided die, and count any 1 result
- as a 2, until the result r is in range. Guess r.
- This isn't perfect, but is good enough in my opinion. There's
- a little game the runner can play with n vs. n - 1 and a large
- bit pool, but it hardly matters in this case anyhow.
- So, how good a card is Social Engineering, anyhow? Looks like
- it's a little better deal than Inside Job in most cases: the
- extra 0.5-1.5 bit expected penalty for choosing an arbitrary
- piece of ice is pretty tasty in a lot of situations. (On the
- other hand, since Inside Job passes the 1st ice it encounters,
- it can be useful in situations where the Corp can't afford to
- rez more than 1 of the several pieces of ice on a fort. Ce'st
- La Vie.) Hopefully, this exposition will help Runners and
- Corps alike deal with Social Engineering, and encourage its use.
- Appendix A: Guess Tables For Social Engineering
- To use these tables: Find the table for the u value you are
- interested in, and go to the column for the n of the bit pool
- you have and are willing to risk. The e value, at the bottom,
- tells how much, including opportunity cost, this Social run
- will cost you. If this is acceptable, then play the Social,
- and roll d100. Pick the row whose entry in your chosen column
- is the largest value less than or equal to the die roll. Look
- to the left to see how many bits to risk.
- u=0
- b= n=03 n=04 n=05 n=06 n=07 n=08 n=09 n=10 n=11 n=12 n=13 n=14 n=15
- 02----59---45---37---33---30---28---26---24---23---22---21---21---20
- 03----99---75---63---56---51---47---44---42---40---38---37---36---34
- 04---------99---83---73---67---62---58---55---52---50---48---47---45
- 05--------------99---87---79---73---69---65---62---60---57---55---54
- 06-------------------99---90---83---78---74---70---67---65---63---61
- 07------------------------99---91---86---81---77---74---72---69---67
- 08-----------------------------99---92---88---84---80---77---75---73
- 09----------------------------------99---93---89---85---82---80---77
- 10---------------------------------------99---94---90---87---84---82
- 11--------------------------------------------99---95---91---88---86
- 12-------------------------------------------------99---95---92---89
- 13------------------------------------------------------99---95---93
- 14-----------------------------------------------------------99---96
- 15----------------------------------------------------------------99
- e= 2.20 1.92 1.78 1.69 1.63 1.58 1.55 1.52 1.50 1.48 1.46 1.44 1.43
- u=1
- b= n=03 n=04 n=05 n=06 n=07 n=08 n=09 n=10 n=11 n=12 n=13 n=14 n=15
- 02----56---41---34---29---26---24---22---20---19---18---18---17---16
- 03----99---73---60---52---46---42---39---37---35---33---32---31---30
- 04---------99---81---70---63---57---53---50---47---45---43---42---40
- 05--------------99---85---77---70---65---61---58---55---53---51---49
- 06-------------------99---88---81---75---70---67---64---61---59---57
- 07------------------------99---90---84---79---74---71---68---65---63
- 08-----------------------------99---92---86---81---78---74---72---69
- 09----------------------------------99---93---88---84---80---77---74
- 10---------------------------------------99---93---89---85---82---79
- 11--------------------------------------------99---94---90---87---84
- 12-------------------------------------------------99---94---91---88
- 13------------------------------------------------------99---95---92
- 14-----------------------------------------------------------99---95
- 15----------------------------------------------------------------99
- e= 2.71 2.28 2.05 1.92 1.82 1.75 1.70 1.66 1.62 1.60 1.57 1.55 1.53
- u=2
- b= n=03 n=04 n=05 n=06 n=07 n=08 n=09 n=10 n=11 n=12 n=13 n=14 n=15
- 02----54---39---31---27---24---21---20---18---17---16---15---15---14
- 03----99---71---58---49---44---40---36---34---32---30---29---28---27
- 04---------99---80---68---60---55---50---47---44---42---40---38---37
- 05--------------99---84---75---68---63---58---55---52---50---48---46
- 06-------------------99---87---79---73---68---64---61---58---56---54
- 07------------------------99---89---82---77---72---69---66---63---60
- 08-----------------------------99---91---85---80---76---72---69---67
- 09----------------------------------99---92---87---82---78---75---72
- 10---------------------------------------99---93---88---84---81---78
- 11--------------------------------------------99---93---89---86---82
- 12-------------------------------------------------99---94---90---87
- 13------------------------------------------------------99---94---91
- 14-----------------------------------------------------------99---95
- 15----------------------------------------------------------------99
- e= 3.22 2.62 2.32 2.13 2.00 1.91 1.84 1.79 1.74 1.71 1.67 1.65 1.62
- u=3
- b= n=03 n=04 n=05 n=06 n=07 n=08 n=09 n=10 n=11 n=12 n=13 n=14 n=15
- 02----53---38---30---25---22---20---18---17---16---15---14---13---13
- 03----99---70---56---48---42---38---34---32---30---28---27---26---24
- 04---------99---79---67---59---53---48---45---42---40---38---36---35
- 05--------------99---84---74---66---61---56---53---50---47---45---43
- 06-------------------99---87---78---72---66---62---59---56---53---51
- 07------------------------99---89---81---76---71---67---64---61---58
- 08-----------------------------99---90---84---79---74---71---68---65
- 09----------------------------------99---91---86---81---77---74---71
- 10---------------------------------------99---92---87---83---79---76
- 11--------------------------------------------99---93---89---85---81
- 12-------------------------------------------------99---94---90---86
- 13------------------------------------------------------99---94---90
- 14-----------------------------------------------------------99---95
- 15----------------------------------------------------------------99
- e= 3.73 2.96 2.58 2.34 2.18 2.07 1.98 1.91 1.86 1.81 1.77 1.74 1.71
- u=4
- b= n=03 n=04 n=05 n=06 n=07 n=08 n=09 n=10 n=11 n=12 n=13 n=14 n=15
- 02----52---37---29---24---21---19---17---16---15---14---13---12---12
- 03----99---70---55---46---41---36---33---30---28---27---25---24---23
- 04---------99---78---66---57---51---47---43---40---38---36---34---33
- 05--------------99---83---73---65---59---55---51---48---46---44---42
- 06-------------------99---86---77---70---65---61---57---54---52---50
- 07------------------------99---88---81---75---70---66---62---59---57
- 08-----------------------------99---90---83---78---73---69---66---63
- 09----------------------------------99---91---85---80---76---73---69
- 10---------------------------------------99---92---87---82---78---75
- 11--------------------------------------------99---93---88---84---80
- 12-------------------------------------------------99---93---89---85
- 13------------------------------------------------------99---94---90
- 14-----------------------------------------------------------99---94
- 15----------------------------------------------------------------99
- e= 4.23 3.30 2.83 2.55 2.36 2.22 2.12 2.03 1.97 1.91 1.86 1.83 1.79
- u=5
- b= n=03 n=04 n=05 n=06 n=07 n=08 n=09 n=10 n=11 n=12 n=13 n=14 n=15
- 02----52---36---28---24---20---18---16---15---14---13---12---12---11
- 03----99---69---54---46---40---35---32---29---27---26---24---23---22
- 04---------99---78---65---57---50---46---42---39---37---35---33---32
- 05--------------99---83---72---64---58---54---50---47---44---42---40
- 06-------------------99---86---77---70---64---60---56---53---50---48
- 07------------------------99---88---80---74---69---65---61---58---55
- 08-----------------------------99---90---83---77---72---68---65---62
- 09----------------------------------99---91---85---80---75---72---68
- 10---------------------------------------99---92---86---82---78---74
- 11--------------------------------------------99---93---88---83---80
- 12-------------------------------------------------99---93---89---85
- 13------------------------------------------------------99---94---90
- 14-----------------------------------------------------------99---94
- 15----------------------------------------------------------------99
- e= 4.73 3.64 3.09 2.75 2.53 2.37 2.25 2.15 2.07 2.01 1.96 1.91 1.87
- u=6
- b= n=03 n=04 n=05 n=06 n=07 n=08 n=09 n=10 n=11 n=12 n=13 n=14 n=15
- 02----51---36---28---23---20---17---16---14---13---12---12---11---10
- 03----99---69---54---45---39---34---31---28---26---25---23---22---21
- 04---------99---77---64---56---50---45---41---38---36---34---32---30
- 05--------------99---82---71---63---57---53---49---46---43---41---39
- 06-------------------99---85---76---69---63---59---55---52---49---47
- 07------------------------99---88---79---73---68---64---60---57---54
- 08-----------------------------99---89---82---76---72---67---64---61
- 09----------------------------------99---91---84---79---74---71---67
- 10---------------------------------------99---92---86---81---77---73
- 11--------------------------------------------99---92---87---83---79
- 12-------------------------------------------------99---93---88---84
- 13------------------------------------------------------99---94---89
- 14-----------------------------------------------------------99---94
- 15----------------------------------------------------------------99
- e= 5.24 3.98 3.34 2.96 2.70 2.52 2.38 2.27 2.18 2.11 2.05 1.00 1.95
- u=7
- b= n=03 n=04 n=05 n=06 n=07 n=08 n=09 n=10 n=11 n=12 n=13 n=14 n=15
- 02----51---35---27---23---19---17---15---14---13---12---11---10---10
- 03----99---68---53---44---38---34---30---28---26---24---22---21---20
- 04---------99---77---64---55---49---44---40---37---35---33---31---30
- 05--------------99---82---71---63---57---52---48---45---42---40---38
- 06-------------------99---85---75---68---63---58---54---51---48---46
- 07------------------------99---87---79---72---67---63---59---56---53
- 08-----------------------------99---89---82---76---71---67---63---60
- 09----------------------------------99---90---84---78---74---70---67
- 10---------------------------------------99---91---85---81---76---73
- 11--------------------------------------------99---92---87---82---78
- 12-------------------------------------------------99---93---88---84
- 13------------------------------------------------------99---93---89
- 14-----------------------------------------------------------99---94
- 15----------------------------------------------------------------99
- e= 5.74 4.31 3.60 3.16 2.87 2.67 2.51 2.39 2.29 2.20 2.14 2.08 2.03
- u=8
- b= n=03 n=04 n=05 n=06 n=07 n=08 n=09 n=10 n=11 n=12 n=13 n=14 n=15
- 02----51---35---27---22---19---17---15---14---12---12---11---10---10
- 03----99---68---53---44---38---33---30---27---25---23---22---21---20
- 04---------99---77---63---55---48---43---40---37---34---32---30---29
- 05--------------99---82---70---62---56---51---47---44---42---39---37
- 06-------------------99---85---75---68---62---57---53---50---48---45
- 07------------------------99---87---79---72---67---62---58---55---53
- 08-----------------------------99---89---81---75---70---66---63---59
- 09----------------------------------99---90---83---78---73---69---66
- 10---------------------------------------99---91---85---80---76---72
- 11--------------------------------------------99---92---87---82---78
- 12-------------------------------------------------99---93---88---83
- 13------------------------------------------------------99---93---89
- 14-----------------------------------------------------------99---94
- 15----------------------------------------------------------------99
- e= 6.24 4.65 3.85 3.37 3.04 2.81 2.64 2.50 2.39 2.30 2.22 2.16 2.10
- u=9
- b= n=03 n=04 n=05 n=06 n=07 n=08 n=09 n=10 n=11 n=12 n=13 n=14 n=15
- 02----51---35---27---22---19---16---15---13---12---11---10---10---09
- 03----99---68---53---43---37---33---29---27---25---23---21---20---19
- 04---------99---76---63---54---48---43---39---36---34---31---30---28
- 05--------------99---81---70---62---55---51---47---44---41---39---37
- 06-------------------99---85---75---67---61---57---53---50---47---44
- 07------------------------99---87---78---72---66---62---58---55---52
- 08-----------------------------99---89---81---75---70---66---62---59
- 09----------------------------------99---90---83---78---73---69---65
- 10---------------------------------------99---91---85---80---75---72
- 11--------------------------------------------99---92---86---82---77
- 12-------------------------------------------------99---93---87---83
- 13------------------------------------------------------99---93---88
- 14-----------------------------------------------------------99---94
- 15----------------------------------------------------------------99
- e= 6.74 4.98 4.09 3.57 3.21 2.96 2.77 2.62 2.50 2.40 2.31 2.24 2.18
- u=10
- b= n=03 n=04 n=05 n=06 n=07 n=08 n=09 n=10 n=11 n=12 n=13 n=14 n=15
- 02----51---34---26---22---18---16---14---13---12---11---10---10---09
- 03----99---68---52---43---37---32---29---26---24---22---21---20---19
- 04---------99---76---63---54---47---42---39---36---33---31---29---28
- 05--------------99---81---70---61---55---50---46---43---40---38---36
- 06-------------------99---84---74---67---61---56---52---49---46---44
- 07------------------------99---87---78---71---66---61---57---54---51
- 08-----------------------------99---89---81---74---69---65---61---58
- 09----------------------------------99---90---83---77---72---68---65
- 10---------------------------------------99---91---85---79---75---71
- 11--------------------------------------------99---92---86---81---77
- 12-------------------------------------------------99---92---87---83
- 13------------------------------------------------------99---93---88
- 14-----------------------------------------------------------99---93
- 15----------------------------------------------------------------99
- e= 7.24 5.32 4.35 3.77 3.38 3.10 2.89 2.73 2.60 2.49 2.40 2.32 2.26
- Appendix B: Algorithms Used In This Article
- Here are the algorithms I used in computing the numbers used in
- the article, including the tables of Appendix A. They are
- written for Keith Packard's "nick" interactive calculator, but
- should be fairly understandable without it.
- function norm(n,u) {
- auto i;
- auto s = 0;
- for (i = 2; i <= n; i++)
- s += 1/(i+u);
- return s;
- }
- function p(i,n,u) {
- return (1/(i+u)) / norm(n,u);
- }
- function ex(n,u) {
- return 1 + 1/norm(n,u);
- }
- function dd(i,n,u) {
- auto j;
- auto s = 0;
- for (j = 2; j <= i; j++)
- s += p(j,n,u);
- return s;
- }
- function d(i,n,u) {
- return floor(dd(i,n,u) * 100) - 1;
- }
- function er(i,n,u) {
- return (1 + i + u) * (1/(n-1) - p(i,n,u));
- }
- function er2(i,n,u) {
- auto k = 1 + i + u;
- if (i == 2)
- return k * (2/n - p(i,n,u));
- else
- return k * (1/n - p(i,n,u));
- }
- function normtest(n,u) {
- auto i;
- auto s = 0;
- for (i = 2; i <= n; i++)
- s += p(i,n,u);
- return s;
- }
- function printtab(u,nn) {
- auto i, n;
- printf("u=%d\n", u);
- printf("b= ");
- for (n = 3; n <= nn; n++)
- printf(" n=%02d", n);
- printf("\n");
- for (i = 2; i <= nn; i++) {
- printf("%02d-", i);
- for (n = 3; n <= nn; n++)
- if (i <= n)
- printf("---%02d", d(i,n,u));
- else
- printf("-----");
- printf("\n");
- }
- printf("e= %4.2f", ex(3,u));
- for (n = 4; n <= nn; n++)
- printf(" %4.2f", ex(n,u));
- printf("\n");
- }
- function printtabs(nu,nn) {
- auto i;
- printtab(0,nn);
- for (i = 1; i <= nu; i++) {
- printf("\n");
- printtab(i,nn);
- }
- }
- /* printtabs(10,15) */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement