10 I.Preliminaries A Recipe Here is a recipe for chocolate mousse,taken from Sinclair and Malinowski's French Cooking (Weathervane Books,1978,p.73).The ingredients-that is,the inputs- include 8 ounces of semisweet chocolate pieces,2 tablespoons of water,a i cup of powdered sugar,6 separated eggs,and so on.The outputs are six to eight servings of delicious mousseline au chocolat.Here is the recipe,or the algorithm for it. Melt chocolate and 2 tablespoons weater in double boiler.When melted,stir in poxdered sugar;add butter bit by bit.Set aside.Beat egg yolks until thick and lemon-colored,about 5 minutes.Gently fold in chocolate.Reheat slightly to melt chocolate,if necessary.Stir in rum and vanilla.Beat egg ihites until foamy. Beat in 2 tablespoons sugar;beat until stiff peaks form.Gently fold whites into chocolate-yolk mixture.Pour into individual serving dishes.Chill at least 4 hours.Serve with ihipped cream,if desired.Makes 6 to 8 servings. This is the "software"relevant to the preparation of the mousse;this is the al- gorithm that controls the process of producing mousse from the ingredients.The process itself is carried out by the"hardware,"in this case the person preparing the mousse,together with the various utensils:the double boiler,the heating apparatus, beater,spoons,timer,and so on. Levels of Detail Let us take a closer look at the most elementary instructions present in this recipe. Consider the instruction"stir in powdered sugar."Why does the recipe not say"take a little powdered sugar,pour it into the melted chocolate,stir it in,take a little more,pour,stir,...?"Even more specifically,why does it not say"take 2365 grains of powdered sugar,pour them into the melted chocolate,pick up a spoon and use circular movements to stir it in,...?"Or,to be even more precise,why not "move your arm towards the ingredients at an angle of 14,at an approximate velocity of 18 inches per second,...?"The answer,of course,is obvious.The hardware knows how to stir powdered sugar into melted chocolate,and does not need further details. Well,how about turning things around and asking whether it is possible that the hard- ware knows how to prepare sugared and buttered chocolate mixture?In such a case, the entire first part of the recipe could be replaced by the simple instruction"prepare chocolate mixture."Taking this to the extreme,maybe the hardware knows how to prepare chocolate mousse.This would make it possible to replace the entire recipe by 'prepare chocolate mousse."Given such a level of hardware expertise,a single line of instruction is a perfect recipe for obtaining mousseline au chocolat;this short recipe is clear,it contains no mistakes,and is guaranteed to produce the desired outputs. Such thought experiments make it clear that the level of detail is very important when it comes to an algorithm's elementary instructions.It must be tailored to fit the hardware's particular capabilities,and should also be appropriate for the comprehension level of a potential reader or user of the algorithm
P1: GIG PE002-01drv PE002-Harel PE002-Harel-v4.cls February 25, 2004 14:38 10 I. Preliminaries ■ A Recipe Here is a recipe for chocolate mousse, taken from Sinclair and Malinowski’s French Cooking (Weathervane Books, 1978, p. 73). The ingredients—that is, the inputs— include 8 ounces of semisweet chocolate pieces, 2 tablespoons of water, a 1 4 cup of powdered sugar, 6 separated eggs, and so on. The outputs are six to eight servings of delicious mousseline au chocolat. Here is the recipe, or the algorithm for it. Melt chocolate and 2 tablespoons water in double boiler. When melted, stir in powdered sugar; add butter bit by bit. Set aside. Beat egg yolks until thick and lemon-colored, about 5 minutes. Gently fold in chocolate. Reheat slightly to melt chocolate, if necessary. Stir in rum and vanilla. Beat egg whites until foamy. Beat in 2 tablespoons sugar; beat until stiff peaks form. Gently fold whites into chocolate-yolk mixture. Pour into individual serving dishes. Chill at least 4 hours. Serve with whipped cream, if desired. Makes 6 to 8 servings. This is the “software” relevant to the preparation of the mousse; this is the algorithm that controls the process of producing mousse from the ingredients. The process itself is carried out by the “hardware,” in this case the person preparing the mousse, together with the various utensils: the double boiler, the heating apparatus, beater, spoons, timer, and so on. ■ Levels of Detail Let us take a closer look at the most elementary instructions present in this recipe. Consider the instruction “stir in powdered sugar.” Why does the recipe not say “take a little powdered sugar, pour it into the melted chocolate, stir it in, take a little more, pour, stir, ...?” Even more specifically, why does it not say “take 2365 grains of powdered sugar, pour them into the melted chocolate, pick up a spoon and use circular movements to stir it in, ...?” Or, to be even more precise, why not “move your arm towards the ingredients at an angle of 14◦, at an approximate velocity of 18 inches per second, ...?” The answer, of course, is obvious. The hardware knows how to stir powdered sugar into melted chocolate, and does not need further details. Well, how about turning things around and asking whether it is possible that the hardware knows how to prepare sugared and buttered chocolate mixture? In such a case, the entire first part of the recipe could be replaced by the simple instruction “prepare chocolate mixture.” Taking this to the extreme, maybe the hardware knows how to prepare chocolate mousse. This would make it possible to replace the entire recipe by “prepare chocolate mousse.” Given such a level of hardware expertise, a single line of instruction is a perfect recipe for obtaining mousseline au chocolat; this short recipe is clear, it contains no mistakes, and is guaranteed to produce the desired outputs. Such thought experiments make it clear that the level of detail is very important when it comes to an algorithm’s elementary instructions. It must be tailored to fit the hardware’s particular capabilities, and should also be appropriate for the comprehension level of a potential reader or user of the algorithm
1.Introduction and Historical Review 11 Consider another example learnt early in our lives,and which is somewhat closer to computation-the orderly multiplication of numbers.Suppose we are asked to multiply 528 by 46.We know exactly what to do.We multiply the 8 by the 6,yielding 48,write down the units digit of the result,8,and remember the tens digit,4;we then multiply the 2 by the 6 and add the 4,yielding 16;we write down the units digit 6 to the left of the 8 and remember the tens digit 1;and so on. Here,the very same questions can be asked.Why "multiply the 8 by the 6?" Why not"look up the entry appearing in the eighth row and sixth column of a multiplication table,"or"add 6 to itself 8 times"?Similarly,why can't we solve the entire problem in one stroke by the simple and satisfactory algorithm"multiply the two numbers?"This last question is rather subtle:why are we allowed to multiply 8 by 6 directly,but not 528 by 46?Again,it is clear that the level of detail is a crucial feature ofour acceptance of the multiplication algorithm.We assume that the relevant hardware (in this case,we ourselves)is capable of carrying out 8 times 6 but not 528 times 46,and that we can do so in our heads,or at least we know of some other way of doing it,so that we do not have to be told how to look up the result in a table. These examples show the need for agreeing right at the start on the basic actions that an algorithm is considered to be capable of prescribing.Without doing so there is no point in trying to find algorithms for anything.Furthermore,different problems are naturally associated with different kinds of basic actions.Recipes entail stirring,mixing,pouring,and heating;multiplying numbers entails addition, digit multiplication,and,significantly,remembering a digit;looking up a telephone number might entail turning a page,moving a finger down a list,and comparing a given name to the one being pointed at. In the precise kinds of algorithms we shall be discussing,these basic instructions must be stated clearly and precisely.We cannot accept things like"beat egg whites until foamy,since one person's idea of foam might be quite unlike another's!In- structions must be adequately distinguishable from non-instructions such as"makes 6 to 8 servings."Fuzzy phrases,such as"about 5 minutes,"have no place in an al- gorithm suited for computer execution,as is the case with ambiguities like"serve with whipped cream,if desired."(Is it the actual serving,or the addition of whipped cream,that depends on the person's desires?)Recipes for mousse,in contrast with the algorithms that will be of interest to us,take too many things for granted,the most notable of which is the fact that a human being is part of the hardware.We cannot depend on that kind of luxury,and hence have to be far more demanding. The overall quality of an algorithm depends crucially on the selection of allowed basic actions and their appropriateness to the matter at hand. Abstraction Earlier it was stated that real computers can only carry out extremely simple opera- tions on extremely simple objects.This might seem to contrast with the present dis- cussion,which recommends that different algorithms be designed using basic actions of varying levels of detail.However,the analogy is still valid.An apprentice chef may need to be given the chocolate mousse recipe,but after a few years of making mousse the instruction"prepare chocolate mousse"will be sufficient.We say that concepts
P1: GIG PE002-01drv PE002-Harel PE002-Harel-v4.cls February 25, 2004 14:38 1. Introduction and Historical Review 11 Consider another example learnt early in our lives, and which is somewhat closer to computation—the orderly multiplication of numbers. Suppose we are asked to multiply 528 by 46. We know exactly what to do. We multiply the 8 by the 6, yielding 48, write down the units digit of the result, 8, and remember the tens digit, 4; we then multiply the 2 by the 6 and add the 4, yielding 16; we write down the units digit 6 to the left of the 8 and remember the tens digit 1; and so on. Here, the very same questions can be asked. Why “multiply the 8 by the 6?” Why not “look up the entry appearing in the eighth row and sixth column of a multiplication table,” or “add 6 to itself 8 times”? Similarly, why can’t we solve the entire problem in one stroke by the simple and satisfactory algorithm “multiply the two numbers?” This last question is rather subtle: why are we allowed to multiply 8 by 6 directly, but not 528 by 46? Again, it is clear that the level of detail is a crucial feature of our acceptance of the multiplication algorithm. We assume that the relevant hardware (in this case, we ourselves) is capable of carrying out 8 times 6 but not 528 times 46, and that we can do so in our heads, or at least we know of some other way of doing it, so that we do not have to be told how to look up the result in a table. These examples show the need for agreeing right at the start on the basic actions that an algorithm is considered to be capable of prescribing. Without doing so there is no point in trying to find algorithms for anything. Furthermore, different problems are naturally associated with different kinds of basic actions. Recipes entail stirring, mixing, pouring, and heating; multiplying numbers entails addition, digit multiplication, and, significantly, remembering a digit; looking up a telephone number might entail turning a page, moving a finger down a list, and comparing a given name to the one being pointed at. In the precise kinds of algorithms we shall be discussing, these basic instructions must be stated clearly and precisely. We cannot accept things like “beat egg whites until foamy,” since one person’s idea of foam might be quite unlike another’s! Instructions must be adequately distinguishable from non-instructions such as “makes 6 to 8 servings.” Fuzzy phrases, such as “about 5 minutes,” have no place in an algorithm suited for computer execution, as is the case with ambiguities like “serve with whipped cream, if desired.” (Is it the actual serving, or the addition of whipped cream, that depends on the person’s desires?) Recipes for mousse, in contrast with the algorithms that will be of interest to us, take too many things for granted, the most notable of which is the fact that a human being is part of the hardware. We cannot depend on that kind of luxury, and hence have to be far more demanding. The overall quality of an algorithm depends crucially on the selection of allowed basic actions and their appropriateness to the matter at hand. ■ Abstraction Earlier it was stated that real computers can only carry out extremely simple operations on extremely simple objects. This might seem to contrast with the present discussion, which recommends that different algorithms be designed using basic actions of varying levels of detail. However, the analogy is still valid. An apprentice chef may need to be given the chocolate mousse recipe, but after a few years of making mousse the instruction “prepare chocolate mousse” will be sufficient. We say that concepts
12 I.Preliminaries like“chocolate mousse,”"lemon meringue,”and“Bavaria cream”are on a higher abstraction level than operations like“mix,”“stir,”and“pour”used in the recipes for making them.In the same way,by appropriate programming,a computer can be made to recognize higher-level abstractions such as numbers,text,and pictures. As in cooking,there are many levels of abstraction in the computer,each appro- priate for describing different kinds of algorithms.For example,the same computer is viewed differently by a 12-year-old playing a computer game,by his sister who is surfing the internet,by his father who is using a spreadsheet program to compute his students'grades,and by his mother who is writing a program for the management of an efficacy trial of a new vaccine.None of them knows or even cares about the bits that really make up the computational process they are using. This process of abstracting away from the details in order to see common patterns in the remainder is at the heart of almost every human endeavor.For example, reading this book has an effect on your brain,which consists of several distinct regions,each of which is composed of neurons and other cells.These cells are built out of complex molecules,which are built out of atoms,which,in turn,are made of more elementary particles.All these different levels of abstraction are relevant to what happens in your brain,but they can't all be considered together.In fact,they belong to different fields of study:particle physics,chemistry,molecular biology, neurobiology,and psychology.A psychologist performing experiments on short- term memory retention will only be distracted by thinking about the relationships between atoms and molecules in the brain. The same is true in computer science.If we were forced to think at the bit level at all times,the computer would hardly be useful.Instead,we can,for example,think of a group of bits(typically eight bits,or a"byte")as denoting a character.We can now consider sequences of bytes to denote English words,sequences of words and punctuation to denote sentences,and so on to paragraphs,chapters,and books.There are algorithms appropriate for each of these levels.For example,spell-checking applies to words but not to characters,left-justification applies to paragraphs,and creating a table of contents applies to books.In each case,we can describe the algo- rithm while completely ignoring the bits that make up the words,the paragraphs,or the entire books.As this book unfolds,and especially in Chapters 3 and 9,we will be discussing the technical means that allow us to make such abstractions.Meanwhile, we shall describe each algorithm on the level of abstraction appropriate for it. Short Algorithms for Long Processes Suppose we are given a list of personnel records,one for each employee in a certain company,each containing the employee's name,personal details,and salary.We are interested in the total sum of all salaries of all employees.Here is an algorithm for carrying out this task: (1)make a note of the number 0; (2)proceed through the list,adding each employee's salary to the noted number; (3)having reached the end of the list,produce the noted number as output
P1: GIG PE002-01drv PE002-Harel PE002-Harel-v4.cls February 25, 2004 14:38 12 I. Preliminaries like “chocolate mousse,” “lemon meringue,” and “Bavaria cream” are on a higher abstraction level than operations like “mix,” “stir,” and “pour” used in the recipes for making them. In the same way, by appropriate programming, a computer can be made to recognize higher-level abstractions such as numbers, text, and pictures. As in cooking, there are many levels of abstraction in the computer, each appropriate for describing different kinds of algorithms. For example, the same computer is viewed differently by a 12-year-old playing a computer game, by his sister who is surfing the internet, by his father who is using a spreadsheet program to compute his students’ grades, and by his mother who is writing a program for the management of an efficacy trial of a new vaccine. None of them knows or even cares about the bits that really make up the computational process they are using. This process of abstracting away from the details in order to see common patterns in the remainder is at the heart of almost every human endeavor. For example, reading this book has an effect on your brain, which consists of several distinct regions, each of which is composed of neurons and other cells. These cells are built out of complex molecules, which are built out of atoms, which, in turn, are made of more elementary particles. All these different levels of abstraction are relevant to what happens in your brain, but they can’t all be considered together. In fact, they belong to different fields of study: particle physics, chemistry, molecular biology, neurobiology, and psychology. A psychologist performing experiments on shortterm memory retention will only be distracted by thinking about the relationships between atoms and molecules in the brain. The same is true in computer science. If we were forced to think at the bit level at all times, the computer would hardly be useful. Instead, we can, for example, think of a group of bits (typically eight bits, or a “byte”) as denoting a character. We can now consider sequences of bytes to denote English words, sequences of words and punctuation to denote sentences, and so on to paragraphs, chapters, and books. There are algorithms appropriate for each of these levels. For example, spell-checking applies to words but not to characters, left-justification applies to paragraphs, and creating a table of contents applies to books. In each case, we can describe the algorithm while completely ignoring the bits that make up the words, the paragraphs, or the entire books. As this book unfolds, and especially in Chapters 3 and 9, we will be discussing the technical means that allow us to make such abstractions. Meanwhile, we shall describe each algorithm on the level of abstraction appropriate for it. ■ Short Algorithms for Long Processes Suppose we are given a list of personnel records, one for each employee in a certain company, each containing the employee’s name, personal details, and salary. We are interested in the total sum of all salaries of all employees. Here is an algorithm for carrying out this task: (1) make a note of the number 0; (2) proceed through the list, adding each employee’s salary to the noted number; (3) having reached the end of the list, produce the noted number as output
1.Introduction and Historical Review 13 Figure 1.3 start Summing salaries. Name Salary 0 Value of noted number John Brown $21.000 21.000 Jack White S34,400 55.400 ● Mike Green s18.000 73,400 Joan Silver $26.000 547.200 end Before proceeding,we should first convince ourselves that this simple algorithm does the job.The"noted"number,which can be thought of as being memorized or written down on a piece of paper,starts out as having the value zero.After carrying out the addition in clause(2)for the first employee,this number actually takes on the value of that employee's salary.After the second employee,its value is the sum of the salaries of the first two employees.At the end,its value is clearly the sum of all salaries(see Figure 1.3). It is interesting that the text of this algorithm is short and fixed in length,but the process it describes and controls varies with the length of the employee list and can be very,very long.Two companies,the first with one employee and the second with a million,can both feed their employee list into the same algorithm,and the salary summation problem will be solved equally well for each.Of course,the process will not take long for the first company,whereas for the second it will be quite lengthy. The algorithm,however,is fixed. Not only is the text of the algorithm short and of fixed size,but both the small and large company require only a single noted number in order to do the job,so that the quantity of"utensils"here is also small and fixed. Of course,the potential value of the noted number will presumably have to be greater for larger companies,but there will be only one number all along. The Algorithmic Problem And so,we have a fixed algorithm prescribing many processes of varying lengths,the precise duration and nature of the process depending on the inputs to the algorithm. Indeed,even the simple example of salary summation shows a variety of possible inputs:one-person companies,companies with a million people,companies in which some of the salaries are zero,or ones in which all salaries are equal.At times an algorithm must also work with bizarre inputs,such as companies with no employees at all,or those that employ people receiving negative salaries (that is,employees who pay the company for the pleasure of working for it). Actually,the salary algorithm is supposed to perform satisfactorily for an infi- nite number of inputs.There is an infinite number of perfectly acceptable lists of
P1: GIG PE002-01drv PE002-Harel PE002-Harel-v4.cls February 25, 2004 14:38 1. Introduction and Historical Review 13 Name Salary John Brown Jack White Mike Green Joan Silver $21,000 21,000 0 Value of noted number start end $34,400 55,400 $18,000 73,400 $26,000 547,200 Figure 1.3 Summing salaries. Before proceeding, we should first convince ourselves that this simple algorithm does the job. The “noted” number, which can be thought of as being memorized or written down on a piece of paper, starts out as having the value zero. After carrying out the addition in clause (2) for the first employee, this number actually takes on the value of that employee’s salary. After the second employee, its value is the sum of the salaries of the first two employees. At the end, its value is clearly the sum of all salaries (see Figure 1.3). It is interesting that the text of this algorithm is short and fixed in length, but the process it describes and controls varies with the length of the employee list and can be very, very long. Two companies, the first with one employee and the second with a million, can both feed their employee list into the same algorithm, and the salary summation problem will be solved equally well for each. Of course, the process will not take long for the first company, whereas for the second it will be quite lengthy. The algorithm, however, is fixed. Not only is the text of the algorithm short and of fixed size, but both the small and large company require only a single noted number in order to do the job, so that the quantity of “utensils” here is also small and fixed. Of course, the potential value of the noted number will presumably have to be greater for larger companies, but there will be only one number all along. ■ ■ ■ The Algorithmic Problem And so, we have a fixed algorithm prescribing many processes of varying lengths, the precise duration and nature of the process depending on the inputs to the algorithm. Indeed, even the simple example of salary summation shows a variety of possible inputs: one-person companies, companies with a million people, companies in which some of the salaries are zero, or ones in which all salaries are equal. At times an algorithm must also work with bizarre inputs, such as companies with no employees at all, or those that employ people receiving negative salaries (that is, employees who pay the company for the pleasure of working for it). Actually, the salary algorithm is supposed to perform satisfactorily for an infi- nite number of inputs. There is an infinite number of perfectly acceptable lists of
14 I.Preliminaries employees,and the algorithm should be able to sum the salaries in any one of them when given as an input. This issue of infinitely many potential inputs does not quite fit the recipe analogy, since although a recipe should work perfectly no matter how many times it is used, its ingredients are usually described as being fixed in quantity,and hence in essence the recipe has only one potential input(at least as quantities go:clearly the molecules and atoms will be different each time).However,the chocolate mousse recipe could have been made generic;that is,its list of ingredients could have read something like "X ounces of chocolate pieces,X/4 tablespoons of water,X/32 cups of powdered sugar,etc.,"and its final line could have been "makes 3X/4 to X servings."This would be more in line with the real notion of an algorithm.In its present form,the recipe is an algorithm of somewhat trivial nature,as it is tailored for one specific set of ingredients.It might be carried out (or,in algorithmic terminology,it might be run or executed)several times,but with essentially the same input,since one cup of flour is considered exactly the same as any other. The input itself has to be legal,relative to the purpose of the algorithm.This means, for example,that the New York Times list of bestsellers would not be acceptable as input to the salary summation algorithm,any more than peanut butter and jelly would be accepted as ingredients for the mousse recipe.This entails some kind of specification of the allowed inputs.Someone must specify precisely which employee lists are legal and which are not;where exactly in the list the salary occurs;whether it is given in longhand (for example,$32,000)or perhaps in some abbreviated form(for example,$32K);where an employee record ends and another begins,and so on. To put it in the most general terms,recipes,or algorithms,are solutions to certain kinds of problems,called computational or algorithmic problems.In the salary example,the problem may be specified in the form of a request for a number that represents the sum of the salaries of a list of employees of an organization.This list may vary in length but must be organized in a particular fashion.Such a problem can be viewed as the search for the contents of a"black box,"which is specified by a precise definition of the legal inputs and a precise definition of the required outputs as a function of those inputs;that is,the way in which each output depends on the input(see Figure 1.4).An algorithmic problem has been solved when an appropriate algorithm has been found.The black box has then actually been provided with contents;it"works"according to that algorithm.In other words,the black box can produce the appropriate output from any legal input by executing the process that is prescribed and governed by that algorithm.The word"any"in the previous sentence is very important.We are not interested in solutions that do not work for all specified inputs.A solution that works well for only some of the legal inputs is easy to come by.As an extreme example,the trivial algorithm: (1)produce 0 as output. works extremely well for several interesting lists of employees:those with no em- ployees at all,those in which everyone earns $0.00(or multiples thereof),as well as those with a payroll that reflects a perfect balance between positive and negative salaries
P1: GIG PE002-01drv PE002-Harel PE002-Harel-v4.cls February 25, 2004 14:38 14 I. Preliminaries employees, and the algorithm should be able to sum the salaries in any one of them when given as an input. This issue of infinitely many potential inputs does not quite fit the recipe analogy, since although a recipe should work perfectly no matter how many times it is used, its ingredients are usually described as being fixed in quantity, and hence in essence the recipe has only one potential input (at least as quantities go; clearly the molecules and atoms will be different each time). However, the chocolate mousse recipe could have been made generic; that is, its list of ingredients could have read something like “X ounces of chocolate pieces, X/4 tablespoons of water, X/32 cups of powdered sugar, etc.,” and its final line could have been “makes 3X/4 to X servings.” This would be more in line with the real notion of an algorithm. In its present form, the recipe is an algorithm of somewhat trivial nature, as it is tailored for one specific set of ingredients. It might be carried out (or, in algorithmic terminology, it might be run or executed) several times, but with essentially the same input, since one cup of flour is considered exactly the same as any other. The input itself has to be legal, relative to the purpose of the algorithm. This means, for example, that the New York Times list of bestsellers would not be acceptable as input to the salary summation algorithm, any more than peanut butter and jelly would be accepted as ingredients for the mousse recipe. This entails some kind of specification of the allowed inputs. Someone must specify precisely which employee lists are legal and which are not; where exactly in the list the salary occurs; whether it is given in longhand (for example, $32,000) or perhaps in some abbreviated form (for example, $32K); where an employee record ends and another begins, and so on. To put it in the most general terms, recipes, or algorithms, are solutions to certain kinds of problems, called computational or algorithmic problems. In the salary example, the problem may be specified in the form of a request for a number that represents the sum of the salaries of a list of employees of an organization. This list may vary in length but must be organized in a particular fashion. Such a problem can be viewed as the search for the contents of a “black box,” which is specified by a precise definition of the legal inputs and a precise definition of the required outputs as a function of those inputs; that is, the way in which each output depends on the input (see Figure 1.4). An algorithmic problem has been solved when an appropriate algorithm has been found. The black box has then actually been provided with contents; it “works” according to that algorithm. In other words, the black box can produce the appropriate output from any legal input by executing the process that is prescribed and governed by that algorithm. The word “any” in the previous sentence is very important. We are not interested in solutions that do not work for all specified inputs. A solution that works well for only some of the legal inputs is easy to come by. As an extreme example, the trivial algorithm: (1) produce 0 as output. works extremely well for several interesting lists of employees: those with no employees at all, those in which everyone earns $0.00 (or multiples thereof ), as well as those with a payroll that reflects a perfect balance between positive and negative salaries