Misplaced Pages

#95904

43-460: Software Arts also developed TK!Solver , a numeric equation solving system originally developed by Milos Konopasek , and Spotlight , "a desktop organizer for the I.B.M. Personal Computer." By early 1984 InfoWorld estimated that Software Arts was the world's 13th-largest microcomputer-software company, with $ 12 million in 1983 sales. It was bought by Lotus in 1985. This article about an IT-related or software-related company or corporation

86-574: A greatest common divisor algorithm presented in Euclid's Elements , Book VII, Proposition 1, finds the remainder given two positive integers using only subtractions and comparisons: The proof that the quotient and remainder exist and are unique (described at Euclidean division ) gives rise to a complete division algorithm, applicable to both negative and positive numbers, using additions, subtractions, and comparisons: This procedure always produces R ≥ 0. Although very simple, it takes Ω(Q) steps, and so

129-437: A computation point of view, the expressions X i + 1 = X i + X i ( 1 − D X i ) {\displaystyle X_{i+1}=X_{i}+X_{i}(1-DX_{i})} and X i + 1 = X i ( 2 − D X i ) {\displaystyle X_{i+1}=X_{i}(2-DX_{i})} are not equivalent. To obtain

172-493: A full-width subtraction. This simplification in turn allows a radix higher than 2 to be used. Like non-restoring division, the final steps are a final full-width subtraction to resolve the last quotient bit, and conversion of the quotient to standard binary form. The Intel Pentium processor's infamous floating-point division bug was caused by an incorrectly coded lookup table. Five of the 1066 entries had been mistakenly omitted. Newton–Raphson uses Newton's method to find

215-523: A programming language like Fortran or APL was superior for simultaneous solution of linear equations . The magazine concluded that despite limitations, it was a "powerful tool, useful for scientists and engineers. No similar product exists". By version 5.0, TK Solver added Matrix handling functionality. Competitive products appeared by mid-1988: Mathsoft's Mathcad and Borland 's Eureka: The Solver . Dan Bricklin , known for VisiCalc and his Software Arts 's initial development of TK Solver,

258-445: A property that becomes extremely valuable when the numbers involved have many digits (e.g. in the large integer domain). But it also means that the initial convergence of the method can be comparatively slow, especially if the initial estimate X 0 {\displaystyle X_{0}} is poorly chosen. For the subproblem of choosing an initial estimate X 0 {\displaystyle X_{0}} , it

301-409: A result with a precision of 2 n bits while making use of the second expression, one must compute the product between X i {\displaystyle X_{i}} and ( 2 − D X i ) {\displaystyle (2-DX_{i})} with double the given precision of X i {\displaystyle X_{i}} ( n bits). In contrast,

344-442: A standard recurrence equation where: Restoring division operates on fixed-point fractional numbers and depends on the assumption 0 < D < N . The quotient digits q are formed from the digit set {0,1}. The basic algorithm for binary (radix 2) restoring division is: Non-performing restoring division is similar to restoring division except that the value of 2R is saved, so D does not need to be added back in for

387-469: A system algebraically by the principle of consecutive substitution. When multiple rules contain multiple unknowns, the program can trigger an iterative solver which uses the Newton–Raphson algorithm to successively approximate based on initial guesses for one or more of the output variables. Procedure functions can also be used to solve systems of equations. Libraries of such procedures are included with

430-575: A user enters an equation, TK Solver can evaluate that equation as is—without isolating unknown variables on one side of the equals sign. Software Arts also released a series of " Solverpacks " - "ready-made versions of some of the formulas most commonly used in specific areas of application." The New York Times described TK Solver as doing "for science and engineering what word processing did for corporate communictions [sic] and calc packages did for finance." Lotus, which had acquired Software Arts, including TK Solver, in 1984 sold its ownership of

473-478: A zero at X = 1 / D {\displaystyle X=1/D} . The obvious such function is f ( X ) = D X − 1 {\displaystyle f(X)=DX-1} , but the Newton–Raphson iteration for this is unhelpful, since it cannot be computed without already knowing the reciprocal of D {\displaystyle D} (moreover it attempts to compute

SECTION 10

#1732876651096

516-459: Is R >> n. (As with restoring division, the low-order bits of R are used up at the same rate as bits of the quotient Q are produced, and it is common to use a single shift register for both.) SRT division is a popular method for division in many microprocessor implementations. The algorithm is named after D. W. Sweeney of IBM , James E. Robertson of University of Illinois , and K. D. Tocher of Imperial College London . They all developed

559-427: Is a stub . You can help Misplaced Pages by expanding it . TK Solver TK Solver (originally TK!Solver ) is a mathematical modeling and problem solving software system based on a declarative , rule-based language , commercialized by Universal Technical Systems, Inc. Invented by Milos Konopasek in the late 1970s and initially developed in 1982 by Software Arts , the company behind VisiCalc , TK Solver

602-424: Is chosen from five possibilities: { −2, −1, 0, +1, +2 }. Because of this, the choice of a quotient digit need not be perfect; later quotient digits can correct for slight errors. (For example, the quotient digit pairs (0, +2) and (1, −2) are equivalent, since 0×4+2 = 1×4−2.) This tolerance allows quotient digits to be selected using only a few most-significant bits of the dividend and divisor, rather than requiring

645-496: Is convenient to apply a bit-shift to the divisor D to scale it so that 0.5 ≤  D  ≤ 1; by applying the same bit-shift to the numerator N , one ensures the quotient does not change. Then one could use a linear approximation in the form to initialize Newton–Raphson. To minimize the maximum of the absolute value of the error of this approximation on interval [ 0.5 , 1 ] {\displaystyle [0.5,1]} , one should use The coefficients of

688-412: Is exponentially slower than even slow division algorithms like long division. It is useful if Q is known to be small (being an output-sensitive algorithm ), and can serve as an executable specification. Long division is the standard algorithm used for pen-and-paper division of multi-digit numbers expressed in decimal notation. It shifts gradually from the left to the right end of the dividend, subtracting

731-560: Is included, with built-in functions for accessing it. TK Solver is also the platform for engineering applications marketed by UTS, including Advanced Spring Design, Integrated Gear Software, Interactive Roark’s Formulas, Heat Transfer on TK, and Dynamics and Vibration Analysis. Tables, plots, comments, and the MathLook notation display tool can be used to enrich TK Solver models. Models can be linked to other components with Microsoft Visual Basic and .NET tools, or they can be web-enabled using

774-551: Is listed and stored on its own worksheet—the Rule Sheet, Variable Sheet, Unit Sheet, etc. Within each worksheet, each object has properties summarized on subsheets or viewed in a property window. The interface uses toolbars and a hierarchal navigation bar that resembles the directory tree seen on the left side of the Windows Explorer . The declarative programming structure is embodied in the rules, functions and variables that form

817-430: Is trivial: perform a ones' complement (bit by bit complement) on the original Q {\displaystyle Q} . Finally, quotients computed by this algorithm are always odd, and the remainder in R is in the range −D ≤ R < D. For example, 5 / 2 = 3 R −1. To convert to a positive remainder, do a single restoring step after Q is converted from non-standard form to standard form: The actual remainder

860-408: The computer time needed for a division is the same, up to a constant factor, as the time needed for a multiplication, whichever multiplication algorithm is used. Discussion will refer to the form N / D = ( Q , R ) {\displaystyle N/D=(Q,R)} , where is the input, and is the output. The simplest division algorithm, historically incorporated into

903-621: The convergence is exactly quadratic, it follows that steps are enough to calculate the value up to P {\displaystyle P\,} binary places. This evaluates to 3 for IEEE single precision and 4 for both double precision and double extended formats. The following computes the quotient of N and D with a precision of P binary places: For example, for a double-precision floating-point division, this method uses 10 multiplies, 9 adds, and 2 shifts. The Newton-Raphson division method can be modified to be slightly faster as follows. After shifting N and D so that D

SECTION 20

#1732876651096

946-480: The reciprocal of D {\displaystyle D} and multiply that reciprocal by N {\displaystyle N} to find the final quotient Q {\displaystyle Q} . The steps of Newton–Raphson division are: In order to apply Newton's method to find the reciprocal of D {\displaystyle D} , it is necessary to find a function f ( X ) {\displaystyle f(X)} that has

989-630: The RuleMaster product or linked with Excel spreadsheets using the Excel Toolkit product. There is also a DesignLink option linking TK Solver models with CAD drawings and solid models. In the premium version, standalone models can be shared with others who do not have a TK license, opening them in Excel or the free TK Player. BYTE in 1984 stated that "TK!Solver is superb for solving almost any kind of equation", but that it did not handle matrices , and that

1032-514: The algorithm independently at approximately the same time (published in February 1957, September 1958, and January 1958 respectively). SRT division is similar to non-restoring division, but it uses a lookup table based on the dividend and the divisor to determine each quotient digit. The most significant difference is that a redundant representation is used for the quotient. For example, when implementing radix-4 SRT division, each quotient digit

1075-553: The case of R < 0. Non-restoring division uses the digit set {−1, 1} for the quotient digits instead of {0, 1}. The algorithm is more complex, but has the advantage when implemented in hardware that there is only one decision and addition/subtraction per quotient bit; there is no restoring step after the subtraction, which potentially cuts down the numbers of operations by up to half and lets it be executed faster. The basic algorithm for binary (radix 2) non-restoring division of non-negative numbers is: Following this algorithm,

1118-585: The core of a mathematical model. All rules are entered in the Rule Sheet or in user-defined functions. Unlike a spreadsheet or imperative programming environment, the rules can be in any order or sequence and are not expressed as assignment statements. "A + B = C / D" is a valid rule in TK Solver and can be solved for any of its four variables. Rules can be added and removed as needed in the Rule Sheet without regard for their order and incorporated into other models. A TK Solver model can include up to 32,000 rules, and

1161-422: The error is defined as ε i = 1 − D X i {\displaystyle \varepsilon _{i}=1-DX_{i}} , then: This squaring of the error at each iteration step – the so-called quadratic convergence of Newton–Raphson's method – has the effect that the number of correct digits in the result roughly doubles for every iteration ,

1204-459: The exact reciprocal in one step, rather than allow for iterative improvements). A function that does work is f ( X ) = ( 1 / X ) − D {\displaystyle f(X)=(1/X)-D} , for which the Newton–Raphson iteration gives which can be calculated from X i {\displaystyle X_{i}} using only multiplication and subtraction, or using two fused multiply–adds . From

1247-480: The final quotient per iteration. Examples of slow division include restoring , non-performing restoring, non-restoring , and SRT division. Fast division methods start with a close approximation to the final quotient and produce twice as many digits of the final quotient on each iteration. Newton–Raphson and Goldschmidt algorithms fall into this category. Variants of these algorithms allow using fast multiplication algorithms . It results that, for large integers,

1290-550: The function at the endpoints, namely, F ( 1 / 2 ) = F ( 1 ) = − F ( − T 1 / ( 2 T 2 ) ) {\displaystyle F(1/2)=F(1)=-F(-T_{1}/(2T_{2}))} . The two equations in the two unknowns have a unique solution T 1 = 48 / 17 {\displaystyle T_{1}=48/17} and T 2 = − 32 / 17 {\displaystyle T_{2}=-32/17} , and

1333-444: The largest possible multiple of the divisor (at the digit level) at each stage; the multiples then become the digits of the quotient, and the final difference is then the remainder. When used with a binary radix, this method forms the basis for the (unsigned) integer division with remainder algorithm below. Short division is an abbreviated form of long division suitable for one-digit divisors. Chunking  – also known as

Software Arts - Misplaced Pages Continue

1376-522: The library that ships with the current version includes utilities for higher mathematics, statistics, engineering and science, finances, and programming. Variables in a rule are automatically posted to the Variable Sheet when the rule is entered and the rule is displayed in mathematical format in the MathLook View window at the bottom of the screen. Any variable can operate as an input or an output, and

1419-1061: The linear approximation are determined as follows. The absolute value of the error is | ε 0 | = | 1 − D ( T 1 + T 2 D ) | {\displaystyle |\varepsilon _{0}|=|1-D(T_{1}+T_{2}D)|} . The minimum of the maximum absolute value of the error is determined by the Chebyshev equioscillation theorem applied to F ( D ) = 1 − D ( T 1 + T 2 D ) {\displaystyle F(D)=1-D(T_{1}+T_{2}D)} . The local minimum of F ( D ) {\displaystyle F(D)} occurs when F ′ ( D ) = 0 {\displaystyle F'(D)=0} , which has solution D = − T 1 / ( 2 T 2 ) {\displaystyle D=-T_{1}/(2T_{2})} . The function at that minimum must be of opposite sign as

1462-548: The maximum error is F ( 1 ) = 1 / 17 {\displaystyle F(1)=1/17} . Using this approximation, the absolute value of the error of the initial value is less than It is possible to generate a polynomial fit of degree larger than 1, computing the coefficients using the Remez algorithm . The trade-off is that the initial guess requires more computational cycles but hopefully in exchange for fewer iterations of Newton–Raphson. Since for this method

1505-604: The model will be solved for the output variables depending on the choice of inputs. A database of unit conversion factors also ships with TK Solver, and users can add, delete, or import unit conversions in a way similar to that for rules. Each variable is associated with a "calculation" unit, but variables can also be assigned "display" units and TK automatically converts the values. For example, rules may be based upon meters and kilograms, but units of inches and pounds can be used for input and output. TK Solver has three ways of solving systems of equations. The "direct solver" solves

1548-407: The partial quotients method or the hangman method – is a less-efficient form of long division which may be easier to understand. By allowing one to subtract more multiples than what one currently has at each stage, a more freeform variant of long division can be developed as well. The following algorithm, the binary version of the famous long division , will divide N by D , placing

1591-413: The product between X i {\displaystyle X_{i}} and ( 1 − D X i ) {\displaystyle (1-DX_{i})} need only be computed with a precision of n bits, because the leading n bits (after the binary point) of ( 1 − D X i ) {\displaystyle (1-DX_{i})} are zeros. If

1634-1061: The program and can be merged into files as needed. A list solver feature allows variables to be associated with ranges of data or probability distributions, solving for multiple values, which is useful for generating tables and plots and for running Monte Carlo simulations . The premium version now also includes a "Solution Optimizer" for direct setting of bounds and constraints in solving models for minimum, maximum, or specific conditions. TK Solver includes roughly 150 built-in functions : mathematical, trigonometric , Boolean , numerical calculus , matrix operations, database access, and programming functions, including string handling and calls to externally compiled routines. Users may also define three types of functions: declarative rule functions; list functions, for table lookups and other operations involving pairs of lists; and procedure functions, for loops and other procedural operations which may also process or result in arrays (lists of lists). The complete NIST database of thermodynamic and transport properties

1677-983: The quotient in Q and the remainder in R . In the following pseudo-code, all values are treated as unsigned integers. If we take N=1100 2 (12 10 ) and D=100 2 (4 10 ) Step 1 : Set R=0 and Q=0 Step 2 : Take i=3 (one less than the number of bits in N) Step 3 : R=00 (left shifted by 1) Step 4 : R=01 (setting R(0) to N(i)) Step 5 : R < D, so skip statement Step 2 : Set i=2 Step 3 : R=010 Step 4 : R=011 Step 5 : R < D, statement skipped Step 2 : Set i=1 Step 3 : R=0110 Step 4 : R=0110 Step 5 : R>=D, statement entered Step 5b : R=10 (R−D) Step 5c : Q=10 (setting Q(i) to 1) Step 2 : Set i=0 Step 3 : R=100 Step 4 : R=100 Step 5 : R>=D, statement entered Step 5b : R=0 (R−D) Step 5c : Q=11 (setting Q(i) to 1) end Q=11 2 (3 10 ) and R=0. Slow division methods are all based on

1720-418: The quotient is in a non-standard form consisting of digits of −1 and +1. This form needs to be converted to binary to form the final quotient. Example: If the −1 digits of Q {\displaystyle Q} are stored as zeros (0) as is common, then P {\displaystyle P} is Q {\displaystyle Q} and computing M {\displaystyle M}

1763-526: The software to Universal Technical Systems less than two years later. Release 5 was still considered "one of the longest–standing mathematical equation solvers on the market today" in 2012. TK Solver's core technologies are a declarative programming language, algebraic equation solver, an iterative equation solver, and a structured, object-based interface, using a command structure. The interface comprises nine classes of objects that can be shared between and merged into other TK files: Each class of object

Software Arts - Misplaced Pages Continue

1806-454: Was acquired by Universal Technical Systems in 1984 after Software Arts fell into financial difficulty and was sold to Lotus Software . Konopasek's goal in inventing the TK Solver concept was to create a problem solving environment in which a given mathematical model built to solve a specific problem could be used to solve related problems (with a redistribution of input and output variables) with minimal or no additional programming required: once

1849-610: Was quoted as saying that the market "wasn't as big as we thought it would be because not that many people think in equations." Newton%E2%80%93Raphson algorithm A division algorithm is an algorithm which, given two integers N and D (respectively the numerator and the denominator), computes their quotient and/or remainder , the result of Euclidean division . Some are applied by hand, while others are employed by digital circuit designs and software. Division algorithms fall into two main categories: slow division and fast division. Slow division algorithms produce one digit of

#95904