What the difference is, between a Native and a Scanned PDF File.

As the subject line suggests, this posting will just define the subject of Native versus Scanned PDF Files.

I have encountered people who simply regard PDF Files as a convenient way to scan a stack of images – from paper – and to store those images. The resulting Scanned PDF Files do have advantages over certain other image formats, such that:

  • They can be password-protected, locked, ‘DRM’ed, etc.,
  • They keep track of a document consisting of more than one actual image, aka page.

But their main disadvantage is, that because they were scanned, they are also rasterized, which means that they have a fixed resolution in pixels. (‘Rasterized’ images are also referred to as ‘Pixel-Maps’ or ‘Bit-Maps’.) I supppose that if a paper document is being scanned, this is not a big deal, because the original document had a limit in its physical level of detail. (:1) But as an alternative, Native PDF Files also exist.

In order to understand what those are, the reader needs to be aware that a form of graphics exists in general, which is an alternative to pixel-based graphics, and that is called ‘Vector-Based Graphics’. What this form of graphics entails is, that there exists a Mathematical definition of a curve, which is often also referred to as a ‘Path’, the parameters of which can be changed from one path to the next. Those parameters need to state in floating-point numbers, where the endpoints of the path are, and, preferably, define what the derivative of the curve is at both endpoints. The most standard type of Mathematical function that does this is a Cubic Spline, but that is by no means the only function available.

A vector-based image consists of a collection of paths, each of which has a different set of these numerical parameters, even in cases where the function is always the same. Also, there often needs to be a stored detail, of how to render such paths, such as to fill in the area inside a closed path with a fill colour, etc..

Continue reading What the difference is, between a Native and a Scanned PDF File.

One weakness of my algorithm, regarding polynomials.

Several months ago, I wrote a C++ program (with C coding-style) that computes numerical approximations, of the roots of an arbitrary polynomial. Even though I changed the code slightly since March, mainly to improve the chances that it will compile on other people’s computers, the basic algorithm hasn’t changed. Yet, because I wrote the algorithm, I know that it has certain weaknesses, and I’m about to divulge one of those…

The main search algorithm isn’t able to determine whether (x) is sufficiently close to a root. It’s really only able to determine whether (y) is sufficiently close to zero. And so an idea that an implementer could have about this would be, to name the maximum allowable error in (x) ‘epsilon’, to compute the derivative of the polynomial for the given value of (x), and then to multiply ‘epsilon’ by this derivative, perhaps naming the derived, allowable error in (y) ‘epsilond’. But I consciously chose not to go that route because:

  • Computing the real derivative of the polynomial each time, though certainly doable, would have made my code complex beyond what I was willing to tolerate,
  • Even had I done so, certain polynomials will have a uselessly low derivative near one of their roots. This can happen because of a doubled root, or simply because of two roots that are too close together. ‘epsilon’ is as small as what would be practical, given the number of bits the variables have to work with, that were, a 52-bit significand.

So my program, instead, computes a ‘notional derivative’ of the polynomial, near (x), that is really just the derivative of the highest exponent by itself. This little detail could actually make it difficult for some observers to understand my code. At the same time, my program limits the lower extent of this derivative, to an arbitrary, modest fraction, just so that (x) won’t need to be impossibly precise, just to satisfy the computation of how precise (y) would need to be.

But then, a predictable problem becomes, that the real derivative of a given polynomial might be much smaller than just, the derivative of this highest exponent. And if it is, then satisfying … for (y) will no longer satisfy … for (x).

The following output illustrates an example of this behaviour:

 


"Maxima" Preparation:

(%i1) expand((x-100)*(x-101)*(x-102));
(%o1) x^3-303*x^2+30602*x-1030200

(%i2) expand((x-100)*(x-110)*(x-120));
(%o2) x^3-330*x^2+36200*x-1320000

(%i3) expand((x-100)*(x-101));
(%o3) x^2-201*x+10100


Approximations from Program:

dirk@Phosphene:~$ poly_solve 1 -303 30602 -1030200

101.00000000013  +  0I
99.999999999938  +  0I
101.99999999993  +  0I


dirk@Phosphene:~$ poly_solve 1 -330 36200 -1320000

100  +  0I
110  +  0I
120  +  0I


dirk@Phosphene:~$ poly_solve 1 -201 10100

100  +  0I
101  +  0I


dirk@Phosphene:~$ 


 

 


 

(Updated 9/22/2019, 5h40 … )

Continue reading One weakness of my algorithm, regarding polynomials.

Some Observations about Roots with Multiplicities.

One of the subjects which I had visited in my past, was to write a C++ program that approximates the roots of polynomials, but that needed to deal with ‘Doubled Roots’ in a special way, just because the search algorithm within that program, which searches for the roots, cannot deal with doubled roots. And what I found was, roots cannot only be doubled, but can have multiplicities higher than (2). After not having pondered that programming project from the past, for some time, I now come back to rethink it, and find that it can be given a lecture of sorts, all to itself.

So, this is a link to a work-sheet, in which I try to explain Roots with Multiplicities, maybe to people with limited knowledge in Calculus:

Link to Letter-Sized PDF

Link to EPUB File, for viewing on Mobile Devices

And as those two documents mention, the following is a link to the earlier blog posting, from which readers can download the C++ program, as well as to find instructions on how to compile it, on Linux computers:

Link to Earlier Blog Posting

Hence, the C++ program linked to in the earlier blog posting, needed to make use of the subject, that the two PDF Files describe.

N.B.:

(Updated 5/06/2019, 13h15 … )

Continue reading Some Observations about Roots with Multiplicities.

How an exact solution can sometimes be found, without using the general solution.

One of the facts which I’ve been writing about is, that the general solution to a polynomial of a degree higher than (4), that is expected to produce Algebraically exact results, cannot be used because none exists. At the same time, I make a distinction between an exact solution, and the general solution. This distinction can also be explained in greater detail…

We are sometimes given a polynomial, which has at least one “rational root”, meaning a root that can be stated either as a whole number, which is actually referred to as an “integer”, or as a fraction. The following is an example:

x^3 -3*x^2 -2*x + 6 = 0

In this case it can be observed, that the coefficient of (x^3), which is not stated, corresponds to a (1), and that the constant term, which is visible as (+6), is an integer. What can be done here, is that all the factors of (6) can be used positively and negatively – not only the prime factors – and plugged in to see whether they do in fact constitute one root. Again, they do if and only if the equation is satisfied as resulting in zero.

Thus, as potential candidates, ±1, ±2, ±3, ±6 can all be tried.

(Updated 3/2/2019, 16h30 … )

Continue reading How an exact solution can sometimes be found, without using the general solution.