Algorithmic efficiency

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Algorithmic_efficiency 

In computer science, algorithmic efficiency is a property of an algorithm which relates to the amount of computational resources used by the algorithm. An algorithm must be analyzed to determine its resource usage, and the efficiency of an algorithm can be measured based on the usage of different resources. Algorithmic efficiency can be thought of as analogous to engineering productivity for a repeating or continuous process.

For maximum efficiency it is desirable to minimize resource usage. However, different resources such as time and space complexity cannot be compared directly, so which of two algorithms is considered to be more efficient often depends on which measure of efficiency is considered most important.

For example, bubble sort and timsort are both algorithms to sort a list of items from smallest to largest. Bubble sort sorts the list in time proportional to the number of elements squared ($O(n^2)$, see Big O notation), but only requires a small amount of extra memory which is constant with respect to the length of the list ($O(1)$). Timsort sorts the list in time linearithmic (proportional to a quantity times its logarithm) in the list's length ($O(n\log n)$), but has a space requirement linear in the length of the list ($O(n)$). If large lists must be sorted at high speed for a given application, timsort is a better choice; however, if minimizing the memory footprint of the sorting is more important, bubble sort is a better choice.

Background

The importance of efficiency with respect to time was emphasised by Ada Lovelace in 1843 as applied to Charles Babbage's mechanical analytical engine:

"In almost every computation a great variety of arrangements for the succession of the processes is possible, and various considerations must influence the selections amongst them for the purposes of a calculating engine. One essential object is to choose that arrangement which shall tend to reduce to a minimum the time necessary for completing the calculation"

Early electronic computers had both limited speed and limited random access memory. Therefore, a space–time trade-off occurred. A task could use a fast algorithm using a lot of memory, or it could use a slow algorithm using little memory. The engineering trade-off was then to use the fastest algorithm that could fit in the available memory.

Modern computers are significantly faster than the early computers, and have a much larger amount of memory available (Gigabytes instead of Kilobytes). Nevertheless, Donald Knuth emphasised that efficiency is still an important consideration:

"In established engineering disciplines a 12% improvement, easily obtained, is never considered marginal and I believe the same viewpoint should prevail in software engineering"

Overview

An algorithm is considered efficient if its resource consumption, also known as computational cost, is at or below some acceptable level. Roughly speaking, 'acceptable' means: it will run in a reasonable amount of time or space on an available computer, typically as a function of the size of the input. Since the 1950s computers have seen dramatic increases in both the available computational power and in the available amount of memory, so current acceptable levels would have been unacceptable even 10 years ago. In fact, thanks to the approximate doubling of computer power every 2 years, tasks that are acceptably efficient on modern smartphones and embedded systems may have been unacceptably inefficient for industrial servers 10 years ago.

Computer manufacturers frequently bring out new models, often with higher performance. Software costs can be quite high, so in some cases the simplest and cheapest way of getting higher performance might be to just buy a faster computer, provided it is compatible with an existing computer.

There are many ways in which the resources used by an algorithm can be measured: the two most common measures are speed and memory usage; other measures could include transmission speed, temporary disk usage, long-term disk usage, power consumption, total cost of ownership, response time to external stimuli, etc. Many of these measures depend on the size of the input to the algorithm, i.e. the amount of data to be processed. They might also depend on the way in which the data is arranged; for example, some sorting algorithms perform poorly on data which is already sorted, or which is sorted in reverse order.

In practice, there are other factors which can affect the efficiency of an algorithm, such as requirements for accuracy and/or reliability. As detailed below, the way in which an algorithm is implemented can also have a significant effect on actual efficiency, though many aspects of this relate to optimization issues.

Theoretical analysis

In the theoretical analysis of algorithms, the normal practice is to estimate their complexity in the asymptotic sense. The most commonly used notation to describe resource consumption or "complexity" is Donald Knuth's Big O notation, representing the complexity of an algorithm as a function of the size of the input $n$. Big O notation is an asymptotic measure of function complexity, where $f(n)=O(g(n))$ roughly means the time requirement for an algorithm is proportional to ${\displaystyle g(n)}$, omitting lower-order terms that contribute less than ${\displaystyle g(n)}$ to the growth of the function as $n$ grows arbitrarily large. This estimate may be misleading when $n$ is small, but is generally sufficiently accurate when $n$ is large as the notation is asymptotic. For example, bubble sort may be faster than merge sort when only a few items are to be sorted; however either implementation is likely to meet performance requirements for a small list. Typically, programmers are interested in algorithms that scale efficiently to large input sizes, and merge sort is preferred over bubble sort for lists of length encountered in most data-intensive programs.

Some examples of Big O notation applied to algorithms' asymptotic time complexity include:

Notation	Name	Examples
${\displaystyle O(1)}$	constant	Finding the median from a sorted list of measurements; Using a constant-size lookup table; Using a suitable hash function for looking up an item.
${\displaystyle O(\log n)}$	logarithmic	Finding an item in a sorted array with a binary search or a balanced search tree as well as all operations in a Binomial heap.
${\displaystyle O(n)}$	linear	Finding an item in an unsorted list or a malformed tree (worst case) or in an unsorted array; Adding two n-bit integers by ripple carry.
${\displaystyle O(n\log n)}$	linearithmic, loglinear, or quasilinear	Performing a Fast Fourier transform; heapsort, quicksort (best and average case), or merge sort
${\displaystyle O(n^2)}$	quadratic	Multiplying two n-digit numbers by a simple algorithm; bubble sort (worst case or naive implementation), Shell sort, quicksort (worst case), selection sort or insertion sort
${\displaystyle O(c^n),c>1}$	exponential	Finding the optimal (non-approximate) solution to the travelling salesman problem using dynamic programming; determining if two logical statements are equivalent using brute-force search

Benchmarking: measuring performance

For new versions of software or to provide comparisons with competitive systems, benchmarks are sometimes used, which assist with gauging an algorithms relative performance. If a new sort algorithm is produced, for example, it can be compared with its predecessors to ensure that at least it is efficient as before with known data, taking into consideration any functional improvements. Benchmarks can be used by customers when comparing various products from alternative suppliers to estimate which product will best suit their specific requirements in terms of functionality and performance. For example, in the mainframe world certain proprietary sort products from independent software companies such as Syncsort compete with products from the major suppliers such as IBM for speed.

Some benchmarks provide opportunities for producing an analysis comparing the relative speed of various compiled and interpreted languages for example and The Computer Language Benchmarks Game compares the performance of implementations of typical programming problems in several programming languages.

Even creating "do it yourself" benchmarks can demonstrate the relative performance of different programming languages, using a variety of user specified criteria. This is quite simple, as a "Nine language performance roundup" by Christopher W. Cowell-Shah demonstrates by example.

Implementation concerns

Implementation issues can also have an effect on efficiency, such as the choice of programming language, or the way in which the algorithm is actually coded, or the choice of a compiler for a particular language, or the compilation options used, or even the operating system being used. In many cases a language implemented by an interpreter may be much slower than a language implemented by a compiler. See the articles on just-in-time compilation and interpreted languages.

There are other factors which may affect time or space issues, but which may be outside of a programmer's control; these include data alignment, data granularity, cache locality, cache coherency, garbage collection, instruction-level parallelism, multi-threading (at either a hardware or software level), simultaneous multitasking, and subroutine calls.

Some processors have capabilities for vector processing, which allow a single instruction to operate on multiple operands; it may or may not be easy for a programmer or compiler to use these capabilities. Algorithms designed for sequential processing may need to be completely redesigned to make use of parallel processing, or they could be easily reconfigured. As parallel and distributed computing grow in importance in the late 2010s, more investments are being made into efficient high-level APIs for parallel and distributed computing systems such as CUDA, TensorFlow, Hadoop, OpenMP and MPI.

Another problem which can arise in programming is that processors compatible with the same instruction set (such as x86-64 or ARM) may implement an instruction in different ways, so that instructions which are relatively fast on some models may be relatively slow on other models. This often presents challenges to optimizing compilers, which must have a great amount of knowledge of the specific CPU and other hardware available on the compilation target to best optimize a program for performance. In the extreme case, a compiler may be forced to emulate instructions not supported on a compilation target platform, forcing it to generate code or link an external library call to produce a result that is otherwise incomputable on that platform, even if it is natively supported and more efficient in hardware on other platforms. This is often the case in embedded systems with respect to floating-point arithmetic, where small and low-power microcontrollers often lack hardware support for floating-point arithmetic and thus require computationally expensive software routines to produce floating point calculations.

Measures of resource usage

Measures are normally expressed as a function of the size of the input ${\displaystyle n}$.

The two most common measures are:

• Time: how long does the algorithm take to complete?
• Space: how much working memory (typically RAM) is needed by the algorithm? This has two aspects: the amount of memory needed by the code (auxiliary space usage), and the amount of memory needed for the data on which the code operates (intrinsic space usage).

For computers whose power is supplied by a battery (e.g. laptops and smartphones), or for very long/large calculations (e.g. supercomputers), other measures of interest are:

• Direct power consumption: power needed directly to operate the computer.
• Indirect power consumption: power needed for cooling, lighting, etc.

As of 2018, power consumption is growing as an important metric for computational tasks of all types and at all scales ranging from embedded Internet of things devices to system-on-chip devices to server farms. This trend is often referred to as green computing.

Less common measures of computational efficiency may also be relevant in some cases:

• Transmission size: bandwidth could be a limiting factor. Data compression can be used to reduce the amount of data to be transmitted. Displaying a picture or image (e.g. Google logo) can result in transmitting tens of thousands of bytes (48K in this case) compared with transmitting six bytes for the text "Google". This is important for I/O bound computing tasks.
• External space: space needed on a disk or other external memory device; this could be for temporary storage while the algorithm is being carried out, or it could be long-term storage needed to be carried forward for future reference.
• Response time (latency): this is particularly relevant in a real-time application when the computer system must respond quickly to some external event.
• Total cost of ownership: particularly if a computer is dedicated to one particular algorithm.

Time

Theory

Analyze the algorithm, typically using time complexity analysis to get an estimate of the running time as a function of the size of the input data. The result is normally expressed using Big O notation. This is useful for comparing algorithms, especially when a large amount of data is to be processed. More detailed estimates are needed to compare algorithm performance when the amount of data is small, although this is likely to be of less importance. Algorithms which include parallel processing may be more difficult to analyze.

Practice

Use a benchmark to time the use of an algorithm. Many programming languages have an available function which provides CPU time usage. For long-running algorithms the elapsed time could also be of interest. Results should generally be averaged over several tests.

Run-based profiling can be very sensitive to hardware configuration and the possibility of other programs or tasks running at the same time in a multi-processing and multi-programming environment.

This sort of test also depends heavily on the selection of a particular programming language, compiler, and compiler options, so algorithms being compared must all be implemented under the same conditions.

Space

This section is concerned with use of memory resources (registers, cache, RAM, virtual memory, secondary memory) while the algorithm is being executed. As for time analysis above, analyze the algorithm, typically using space complexity analysis to get an estimate of the run-time memory needed as a function as the size of the input data. The result is normally expressed using Big O notation.

There are up to four aspects of memory usage to consider:

• The amount of memory needed to hold the code for the algorithm.
• The amount of memory needed for the input data.
• The amount of memory needed for any output data.
  • Some algorithms, such as sorting, often rearrange the input data and don't need any additional space for output data. This property is referred to as "in-place" operation.
• The amount of memory needed as working space during the calculation.
  • This includes local variables and any stack space needed by routines called during a calculation; this stack space can be significant for algorithms which use recursive techniques.

Early electronic computers, and early home computers, had relatively small amounts of working memory. For example, the 1949 Electronic Delay Storage Automatic Calculator (EDSAC) had a maximum working memory of 1024 17-bit words, while the 1980 Sinclair ZX80 came initially with 1024 8-bit bytes of working memory. In the late 2010s, it is typical for personal computers to have between 4 and 32 GB of RAM, an increase of over 300 million times as much memory.

Caching and memory hierarchy

Further information: Memory hierarchy

Current computers can have relatively large amounts of memory (possibly Gigabytes), so having to squeeze an algorithm into a confined amount of memory is much less of a problem than it used to be. But the presence of four different categories of memory can be significant:

• Processor registers, the fastest of computer memory technologies with the least amount of storage space. Most direct computation on modern computers occurs with source and destination operands in registers before being updated to the cache, main memory and virtual memory if needed. On a processor core, there are typically on the order of hundreds of bytes or fewer of register availability, although a register file may contain more physical registers than architectural registers defined in the instruction set architecture.
• Cache memory is the second fastest and second smallest memory available in the memory hierarchy. Caches are present in CPUs, GPUs, hard disk drives and external peripherals, and are typically implemented in static RAM. Memory caches are multi-leveled; lower levels are larger, slower and typically shared between processor cores in multi-core processors. In order to process operands in cache memory, a processing unit must fetch the data from the cache, perform the operation in registers and write the data back to the cache. This operates at speeds comparable (about 2-10 times slower) with the CPU or GPU's arithmetic logic unit or floating-point unit if in the L1 cache. It is about 10 times slower if there is an L1 cache miss and it must be retrieved from and written to the L2 cache, and a further 10 times slower if there is an L2 cache miss and it must be retrieved from an L3 cache, if present.
• Main physical memory is most often implemented in dynamic RAM (DRAM). The main memory is much larger (typically gigabytes compared to ≈8 megabytes) than an L3 CPU cache, with read and write latencies typically 10-100 times slower. As of 2018, RAM is increasingly implemented on-chip of processors, as CPU or GPU memory.
• Virtual memory is most often implemented in terms of secondary storage such as a hard disk, and is an extension to the memory hierarchy that has much larger storage space but much larger latency, typically around 1000 times slower than a cache miss for a value in RAM. While originally motivated to create the impression of higher amounts of memory being available than were truly available, virtual memory is more important in contemporary usage for its time-space tradeoff and enabling the usage of virtual machines. Cache misses from main memory are called page faults, and incur huge performance penalties on programs.

An algorithm whose memory needs will fit in cache memory will be much faster than an algorithm which fits in main memory, which in turn will be very much faster than an algorithm which has to resort to virtual memory. Because of this, cache replacement policies are extremely important to high-performance computing, as are cache-aware programming and data alignment. To further complicate the issue, some systems have up to three levels of cache memory, with varying effective speeds. Different systems will have different amounts of these various types of memory, so the effect of algorithm memory needs can vary greatly from one system to another.

In the early days of electronic computing, if an algorithm and its data wouldn't fit in main memory then the algorithm couldn't be used. Nowadays the use of virtual memory appears to provide much memory, but at the cost of performance. If an algorithm and its data will fit in cache memory, then very high speed can be obtained; in this case minimizing space will also help minimize time. This is called the principle of locality, and can be subdivided into locality of reference, spatial locality and temporal locality. An algorithm which will not fit completely in cache memory but which exhibits locality of reference may perform reasonably well.

Criticism of the current state of programming

• David May FRS a British computer scientist and currently Professor of Computer Science at University of Bristol and founder and CTO of XMOS Semiconductor, believes one of the problems is that there is a reliance on Moore's law to solve inefficiencies. He has advanced an 'alternative' to Moore's law (May's law) stated as follows:

Software efficiency halves every 18 months, compensating Moore's Law

May goes on to state:

In ubiquitous systems, halving the instructions executed can double the battery life and big data sets bring big opportunities for better software and algorithms: Reducing the number of operations from N × N to N × log(N) has a dramatic effect when N is large ... for N = 30 billion, this change is as good as 50 years of technology improvements.

• Software author Adam N. Rosenburg in his blog "The failure of the Digital computer", has described the current state of programming as nearing the "Software event horizon", (alluding to the fictitious "shoe event horizon" described by Douglas Adams in his Hitchhiker's Guide to the Galaxy book). He estimates there has been a 70 dB factor loss of productivity or "99.99999 percent, of its ability to deliver the goods", since the 1980s—"When Arthur C. Clarke compared the reality of computing in 2001 to the computer HAL 9000 in his book 2001: A Space Odyssey, he pointed out how wonderfully small and powerful computers were but how disappointing computer programming had become".

Competitions for the best algorithms

The following competitions invite entries for the best algorithms based on some arbitrary criteria decided by the judges:

• Wired magazine

Intuitionism

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Intuitionism 

In the philosophy of mathematics, intuitionism, or neointuitionism (opposed to preintuitionism), is an approach where mathematics is considered to be purely the result of the constructive mental activity of humans rather than the discovery of fundamental principles claimed to exist in an objective reality. That is, logic and mathematics are not considered analytic activities wherein deep properties of objective reality are revealed and applied, but are instead considered the application of internally consistent methods used to realize more complex mental constructs, regardless of their possible independent existence in an objective reality.

Truth and proof

The fundamental distinguishing characteristic of intuitionism is its interpretation of what it means for a mathematical statement to be true. In Brouwer's original intuitionism, the truth of a mathematical statement is a subjective claim: a mathematical statement corresponds to a mental construction, and a mathematician can assert the truth of a statement only by verifying the validity of that construction by intuition. The vagueness of the intuitionistic notion of truth often leads to misinterpretations about its meaning. Kleene formally defined intuitionistic truth from a realist position, yet Brouwer would likely reject this formalization as meaningless, given his rejection of the realist/Platonist position. Intuitionistic truth therefore remains somewhat ill-defined. However, because the intuitionistic notion of truth is more restrictive than that of classical mathematics, the intuitionist must reject some assumptions of classical logic to ensure that everything they prove is in fact intuitionistically true. This gives rise to intuitionistic logic.

To an intuitionist, the claim that an object with certain properties exists is a claim that an object with those properties can be constructed. Any mathematical object is considered to be a product of a construction of a mind, and therefore, the existence of an object is equivalent to the possibility of its construction. This contrasts with the classical approach, which states that the existence of an entity can be proved by refuting its non-existence. For the intuitionist, this is not valid; the refutation of the non-existence does not mean that it is possible to find a construction for the putative object, as is required in order to assert its existence. As such, intuitionism is a variety of mathematical constructivism; but it is not the only kind.

The interpretation of negation is different in intuitionist logic than in classical logic. In classical logic, the negation of a statement asserts that the statement is false; to an intuitionist, it means the statement is refutable. There is thus an asymmetry between a positive and negative statement in intuitionism. If a statement P is provable, then P certainly cannot be refutable. But even if it can be shown that P cannot be refuted, this does not constitute a proof of P. Thus P is a stronger statement than not-not-P.

Similarly, to assert that A or B holds, to an intuitionist, is to claim that either A or B can be proved. In particular, the law of excluded middle, "A or not A", is not accepted as a valid principle. For example, if A is some mathematical statement that an intuitionist has not yet proved or disproved, then that intuitionist will not assert the truth of "A or not A". However, the intuitionist will accept that "A and not A" cannot be true. Thus the connectives "and" and "or" of intuitionistic logic do not satisfy de Morgan's laws as they do in classical logic.

Intuitionistic logic substitutes constructability for abstract truth and is associated with a transition from the proof of model theory to abstract truth in modern mathematics. The logical calculus preserves justification, rather than truth, across transformations yielding derived propositions. It has been taken as giving philosophical support to several schools of philosophy, most notably the Anti-realism of Michael Dummett. Thus, contrary to the first impression its name might convey, and as realized in specific approaches and disciplines (e.g. Fuzzy Sets and Systems), intuitionist mathematics is more rigorous than conventionally founded mathematics, where, ironically, the foundational elements which Intuitionism attempts to construct/refute/refound are taken as intuitively given.

Infinity

Among the different formulations of intuitionism, there are several different positions on the meaning and reality of infinity.

The term potential infinity refers to a mathematical procedure in which there is an unending series of steps. After each step has been completed, there is always another step to be performed. For example, consider the process of counting: 1, 2, 3, ...

The term actual infinity refers to a completed mathematical object which contains an infinite number of elements. An example is the set of natural numbers, N = {1, 2, ...}.

In Cantor's formulation of set theory, there are many different infinite sets, some of which are larger than others. For example, the set of all real numbers R is larger than N, because any procedure that you attempt to use to put the natural numbers into one-to-one correspondence with the real numbers will always fail: there will always be an infinite number of real numbers "left over". Any infinite set that can be placed in one-to-one correspondence with the natural numbers is said to be "countable" or "denumerable". Infinite sets larger than this are said to be "uncountable".

Cantor's set theory led to the axiomatic system of Zermelo–Fraenkel set theory (ZFC), now the most common foundation of modern mathematics. Intuitionism was created, in part, as a reaction to Cantor's set theory.

Modern constructive set theory includes the axiom of infinity from ZFC (or a revised version of this axiom) and the set N of natural numbers. Most modern constructive mathematicians accept the reality of countably infinite sets (however, see Alexander Esenin-Volpin for a counter-example).

Brouwer rejected the concept of actual infinity, but admitted the idea of potential infinity.

"According to Weyl 1946, 'Brouwer made it clear, as I think beyond any doubt, that there is no evidence supporting the belief in the existential character of the totality of all natural numbers ... the sequence of numbers which grows beyond any stage already reached by passing to the next number, is a manifold of possibilities open towards infinity; it remains forever in the status of creation, but is not a closed realm of things existing in themselves. That we blindly converted one into the other is the true source of our difficulties, including the antinomies – a source of more fundamental nature than Russell's vicious circle principle indicated. Brouwer opened our eyes and made us see how far classical mathematics, nourished by a belief in the 'absolute' that transcends all human possibilities of realization, goes beyond such statements as can claim real meaning and truth founded on evidence." (Kleene (1952): Introduction to Metamathematics, p. 48-49)

History

Intuitionism's history can be traced to two controversies in nineteenth century mathematics.

The first of these was the invention of transfinite arithmetic by Georg Cantor and its subsequent rejection by a number of prominent mathematicians including most famously his teacher Leopold Kronecker—a confirmed finitist.

The second of these was Gottlob Frege's effort to reduce all of mathematics to a logical formulation via set theory and its derailing by a youthful Bertrand Russell, the discoverer of Russell's paradox. Frege had planned a three volume definitive work, but just as the second volume was going to press, Russell sent Frege a letter outlining his paradox, which demonstrated that one of Frege's rules of self-reference was self-contradictory. In an appendix to the second volume, Frege acknowledged that one of the axioms of his system did in fact lead to Russell's paradox.

Frege, the story goes, plunged into depression and did not publish the third volume of his work as he had planned. For more see Davis (2000) Chapters 3 and 4: Frege: From Breakthrough to Despair and Cantor: Detour through Infinity. See van Heijenoort for the original works and van Heijenoort's commentary.

These controversies are strongly linked as the logical methods used by Cantor in proving his results in transfinite arithmetic are essentially the same as those used by Russell in constructing his paradox. Hence how one chooses to resolve Russell's paradox has direct implications on the status accorded to Cantor's transfinite arithmetic.

In the early twentieth century L. E. J. Brouwer represented the intuitionist position and David Hilbert the formalist position—see van Heijenoort. Kurt Gödel offered opinions referred to as Platonist (see various sources re Gödel). Alan Turing considers: "non-constructive systems of logic with which not all the steps in a proof are mechanical, some being intuitive". (Turing 1939, reprinted in Davis 2004, p. 210) Later, Stephen Cole Kleene brought forth a more rational consideration of intuitionism in his Introduction to Meta-mathematics (1952).

Nicolas Gisin is adopting intuitionist mathematics to reinterpret quantum indeterminacy, information theory and the physics of time.

Contributors

• Henri Poincaré (preintuitionism/conventionalism)
• L. E. J. Brouwer
• Michael Dummett
• Arend Heyting
• Stephen Kleene

Branches of intuitionistic mathematics

• Intuitionistic logic
• Intuitionistic arithmetic
• Intuitionistic type theory
• Intuitionistic set theory
• Intuitionistic analysis

Thermionic emission

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Thermionic_emission 

 

Closeup of the filament in a low pressure mercury gas-discharge lamp showing white thermionic emission mix coating on the central portion of the coil. Typically made of a mixture of barium, strontium, and calcium oxides, the coating is sputtered away through normal use, often eventually resulting in lamp failure.

 

One of the bulbs with which Edison discovered thermionic emission. It consists of an evacuated glass light bulb containing a carbon filament (hairpin shape), with an additional metal plate attached to wires emerging from the base. Electrons released by the filament were attracted to the plate when it had a positive voltage.

Thermionic emission is the liberation of electrons from an electrode by virtue of its temperature (releasing of energy supplied by heat). This occurs because the thermal energy given to the charge carrier overcomes the work function of the material. The charge carriers can be electrons or ions, and in older literature are sometimes referred to as thermions. After emission, a charge that is equal in magnitude and opposite in sign to the total charge emitted is initially left behind in the emitting region. But if the emitter is connected to a battery, the charge left behind is neutralized by charge supplied by the battery as the emitted charge carriers move away from the emitter, and finally the emitter will be in the same state as it was before emission.

The classical example of thermionic emission is that of electrons from a hot cathode into a vacuum (also known as thermal electron emission or the Edison effect) in a vacuum tube. The hot cathode can be a metal filament, a coated metal filament, or a separate structure of metal or carbides or borides of transition metals. Vacuum emission from metals tends to become significant only for temperatures over 1,000 K (730 °C; 1,340 °F).

This process is crucially important in the operation of a variety of electronic devices and can be used for electricity generation (such as thermionic converters and electrodynamic tethers) or cooling. The magnitude of the charge flow increases dramatically with increasing temperature.

The term 'thermionic emission' is now also used to refer to any thermally-excited charge emission process, even when the charge is emitted from one solid-state region into another.

History

The Edison effect in a diode tube. A diode tube is connected in two configurations; one has a flow of electrons and the other does not. (The arrows represent electron current, not conventional current.)

Because the electron was not identified as a separate physical particle until the work of J. J. Thomson in 1897, the word "electron" was not used when discussing experiments that took place before this date.

The phenomenon was initially reported in 1853 by Edmond Becquerel. It was rediscovered in 1873 by Frederick Guthrie in Britain. While doing work on charged objects, Guthrie discovered that a red-hot iron sphere with a negative charge would lose its charge (by somehow discharging it into air). He also found that this did not happen if the sphere had a positive charge. Other early contributors included Johann Wilhelm Hittorf (1869–1883), Eugen Goldstein (1885), and Julius Elster and Hans Friedrich Geitel (1882–1889).

The effect was rediscovered again by Thomas Edison on February 13, 1880, while he was trying to discover the reason for breakage of lamp filaments and uneven blackening (darkest near the positive terminal of the filament) of the bulbs in his incandescent lamps.

Edison built several experimental lamp bulbs with an extra wire, metal plate, or foil inside the bulb that was separate from the filament and thus could serve as an electrode. He connected a galvanometer, a device used to measure current (the flow of charge), to the output of the extra metal electrode. If the foil was put at a negative potential relative to the filament, there was no measurable current between the filament and the foil. When the foil was raised to a positive potential relative to the filament, there could be a significant current between the filament through the vacuum to the foil if the filament was heated sufficiently (by its own external power source).

We now know that the filament was emitting electrons, which were attracted to a positively charged foil, but not a negatively charged one. This one-way current was called the Edison effect (although the term is occasionally used to refer to thermionic emission itself). He found that the current emitted by the hot filament increased rapidly with increasing voltage, and filed a patent application for a voltage-regulating device using the effect on November 15, 1883 (U.S. patent 307,031, the first US patent for an electronic device). He found that sufficient current would pass through the device to operate a telegraph sounder. This was exhibited at the International Electrical Exposition in Philadelphia in September 1884. William Preece, a British scientist, took back with him several of the Edison effect bulbs. He presented a paper on them in 1885, where he referred to thermionic emission as the "Edison effect." The British physicist John Ambrose Fleming, working for the British "Wireless Telegraphy" Company, discovered that the Edison effect could be used to detect radio waves. Fleming went on to develop the two-element vacuum tube known as the diode, which he patented on November 16, 1904.

The thermionic diode can also be configured as a device that converts a heat difference to electric power directly without moving parts (a thermionic converter, a type of heat engine).

Richardson's law

Following J. J. Thomson's identification of the electron in 1897, the British physicist Owen Willans Richardson began work on the topic that he later called "thermionic emission". He received a Nobel Prize in Physics in 1928 "for his work on the thermionic phenomenon and especially for the discovery of the law named after him".

From band theory, there are one or two electrons per atom in a solid that are free to move from atom to atom. This is sometimes collectively referred to as a "sea of electrons". Their velocities follow a statistical distribution, rather than being uniform, and occasionally an electron will have enough velocity to exit the metal without being pulled back in. The minimum amount of energy needed for an electron to leave a surface is called the work function. The work function is characteristic of the material and for most metals is on the order of several electronvolts. Thermionic currents can be increased by decreasing the work function. This often-desired goal can be achieved by applying various oxide coatings to the wire.

In 1901 Richardson published the results of his experiments: the current from a heated wire seemed to depend exponentially on the temperature of the wire with a mathematical form similar to the Arrhenius equation. Later, he proposed that the emission law should have the mathematical form

${\displaystyle J=A_{\mathrm{G}}{T}^2{\mathrm{e}}^{\frac{-W}{kT}}}$

where J is the emission current density, T is the temperature of the metal, W is the work function of the metal, k is the Boltzmann constant, and A_G is a parameter discussed next.

In the period 1911 to 1930, as physical understanding of the behaviour of electrons in metals increased, various theoretical expressions (based on different physical assumptions) were put forward for A_G, by Richardson, Saul Dushman, Ralph H. Fowler, Arnold Sommerfeld and Lothar Wolfgang Nordheim. Over 60 years later, there is still no consensus among interested theoreticians as to the exact expression of A_G, but there is agreement that A_G must be written in the form

${\displaystyle A_{\mathrm{G}}={\lambda }_{\mathrm{R}}{A}_0}$

where λ_R is a material-specific correction factor that is typically of order 0.5, and A₀ is a universal constant given by

${\displaystyle A_0=\frac{4\pi m{k}^2{q}_e}{h^3}=1.20173\times {10}^6\mathrm{A}{\mathrm{m}}^{-2}{\mathrm{K}}^{-2}}$

where m and ${\displaystyle -q_e}$ are the mass and charge of an electron, respectively, and h is Planck's constant.

In fact, by about 1930 there was agreement that, due to the wave-like nature of electrons, some proportion r_av of the outgoing electrons would be reflected as they reached the emitter surface, so the emission current density would be reduced, and λ_R would have the value (1-r_av). Thus, one sometimes sees the thermionic emission equation written in the form

${\displaystyle J=(1-r_{\mathrm{a}\mathrm{v}}){\lambda }_B{A}_0{T}^2{\mathrm{e}}^{\frac{-W}{kT}}}$.

However, a modern theoretical treatment by Modinos assumes that the band-structure of the emitting material must also be taken into account. This would introduce a second correction factor λ_B into λ_R, giving ${\displaystyle A_{\mathrm{G}}={\lambda }_{\mathrm{B}}(1-r_{\mathrm{a}\mathrm{v}})A_0}$. Experimental values for the "generalized" coefficient A_G are generally of the order of magnitude of A₀, but do differ significantly as between different emitting materials, and can differ as between different crystallographic faces of the same material. At least qualitatively, these experimental differences can be explained as due to differences in the value of λ_R.

Considerable confusion exists in the literature of this area because: (1) many sources do not distinguish between A_G and A₀, but just use the symbol A (and sometimes the name "Richardson constant") indiscriminately; (2) equations with and without the correction factor here denoted by λ_R are both given the same name; and (3) a variety of names exist for these equations, including "Richardson equation", "Dushman's equation", "Richardson–Dushman equation" and "Richardson–Laue–Dushman equation". In the literature, the elementary equation is sometimes given in circumstances where the generalized equation would be more appropriate, and this in itself can cause confusion. To avoid misunderstandings, the meaning of any "A-like" symbol should always be explicitly defined in terms of the more fundamental quantities involved.

Because of the exponential function, the current increases rapidly with temperature when kT is less than W. (For essentially every material, melting occurs well before kT = W.)

The thermionic emission law has been recently revised for 2D materials in various models.

Schottky emission

Main article: Schottky effect

 

Schottky-emitter electron source of an electron microscope

In electron emission devices, especially electron guns, the thermionic electron emitter will be biased negative relative to its surroundings. This creates an electric field of magnitude E at the emitter surface. Without the field, the surface barrier seen by an escaping Fermi-level electron has height W equal to the local work-function. The electric field lowers the surface barrier by an amount ΔW, and increases the emission current. This is known as the Schottky effect (named for Walter H. Schottky) or field enhanced thermionic emission. It can be modeled by a simple modification of the Richardson equation, by replacing W by (W − ΔW). This gives the equation

${\displaystyle J(F,T,W)=A_{\mathrm{G}}{T}^2{e}^{\frac{-(W-\mathrm{\Delta }W)}{kT}}}$

${\displaystyle \mathrm{\Delta }W=\sqrt{\frac{{q_e}^{3}E}{4\pi {ϵ}_0}},}$

where ε₀ is the electric constant (also, formerly, called the vacuum permittivity).

Electron emission that takes place in the field-and-temperature-regime where this modified equation applies is often called Schottky emission. This equation is relatively accurate for electric field strengths lower than about 10⁸ V  m⁻¹. For electric field strengths higher than 10⁸ V m⁻¹, so-called Fowler-Nordheim (FN) tunneling begins to contribute significant emission current. In this regime, the combined effects of field-enhanced thermionic and field emission can be modeled by the Murphy-Good equation for thermo-field (T-F) emission. At even higher fields, FN tunneling becomes the dominant electron emission mechanism, and the emitter operates in the so-called "cold field electron emission (CFE)" regime.

Thermionic emission can also be enhanced by interaction with other forms of excitation such as light. For example, excited Cs-vapours in thermionic converters form clusters of Cs-Rydberg matter which yield a decrease of collector emitting work function from 1.5 eV to 1.0–0.7 eV. Due to long-lived nature of Rydberg matter this low work function remains low which essentially increases the low-temperature converter's efficiency.

Photon-enhanced thermionic emission

Photon-enhanced thermionic emission (PETE) is a process developed by scientists at Stanford University that harnesses both the light and heat of the sun to generate electricity and increases the efficiency of solar power production by more than twice the current levels. The device developed for the process reaches peak efficiency above 200 °C, while most silicon solar cells become inert after reaching 100 °C. Such devices work best in parabolic dish collectors, which reach temperatures up to 800 °C. Although the team used a gallium nitride semiconductor in its proof-of-concept device, it claims that the use of gallium arsenide can increase the device's efficiency to 55–60 percent, nearly triple that of existing systems, and 12–17 percent more than existing 43 percent multi-junction solar cells.