text:
# August, 2010

• #### Everybody thinks about garbage collection the wrong way

Welcome to CLR Week 2010. This year, CLR Week is going to be more philosophical than usual.

When you ask somebody what garbage collection is, the answer you get is probably going to be something along the lines of "Garbage collection is when the operating environment automatically reclaims memory that is no longer being used by the program. It does this by tracing memory starting from roots to identify which objects are accessible."

This description confuses the mechanism with the goal. It's like saying the job of a firefighter is "driving a red truck and spraying water." That's a description of what a firefighter does, but it misses the point of the job (namely, putting out fires and, more generally, fire safety).

Garbage collection is simulating a computer with an infinite amount of memory. The rest is mechanism. And naturally, the mechanism is "reclaiming memory that the program wouldn't notice went missing." It's one giant application of the as-if rule.¹

Now, with this view of the true definition of garbage collection, one result immediately follows:

If the amount of RAM available to the runtime is greater than the amount of memory required by a program, then a memory manager which employs the null garbage collector (which never collects anything) is a valid memory manager.

This is true because the memory manager can just allocate more RAM whenever the program needs it, and by assumption, this allocation will always succeed. A computer with more RAM than the memory requirements of a program has effectively infinite RAM, and therefore no simulation is needed.

Sure, the statement may be obvious, but it's also useful, because the null garbage collector is both very easy to analyze yet very different from garbage collectors you're more accustomed to seeing. You can therefore use it to produce results like this:

A correctly-written program cannot assume that finalizers will ever run at any point prior to program termination.

The proof of this is simple: Run the program on a machine with more RAM than the amount of memory required by program. Under these circumstances, the null garbage collector is a valid garbage collector, and the null garbage collector never runs finalizers since it never collects anything.

Garbage collection simulates infinite memory, but there are things you can do even if you have infinite memory that have visible effects on other programs (and possibly even on your program). If you open a file in exclusive mode, then the file will not be accessible to other programs (or even to other parts of your own program) until you close it. A connection that you open to a SQL server consumes resources in the server until you close it. Have too many of these connections outstanding, and you may run into a connection limit which blocks further connections. If you don't explicitly close these resources, then when your program is run on a machine with "infinite" memory, those resources will accumulate and never be released.

What this means for you: Your programs cannot rely on finalizers keeping things tidy. Finalizers are a safety net, not a primary means for resource reclamation. When you are finished with a resource, you need to release it by calling Close or Disconnect or whatever cleanup method is available on the object. (The IDisposable interface codifies this convention.)

Furthermore, it turns out that not only can a correctly-written program not assume that finalizers will run during the execution of a program, it cannot even assume that finalizers will run when the program terminates: Although the .NET Framework will try to run them all, a bad finalizer will cause the .NET Framework to give up and abandon running finalizers. This can happen through no fault of your own: There might be a handle to a network resource that the finalizer is trying to release, but network connectivity problems result in the operation taking longer than two seconds, at which point the .NET Framework will just terminate the process. Therefore, the above result can be strengthened in the specific case of the .NET Framework:

A correctly-written program cannot assume that finalizers will ever run.

Armed with this knowledge, you can solve this customer's problem. (Confusing terminology is preserved from the original.)

I have a class that uses XmlDocument. After the class is out of scope, I want to delete the file, but I get the exception System.IO.Exception: The process cannot access the file 'C:\path\to\file.xml' because it is being used by another process. Once the progam exits, then the lock goes away. Is there any way to avoid locking the file?

This follow-up might or might not help:

A colleague suggested setting the XmlDocument variables to null when we're done with them, but shouldn't leaving the class scope have the same behavior?

Bonus chatter: Finalizers are weird, since they operate "behind the GC." There are also lots of classes which operate "at the GC level", such as WeakReference GCHandle and of course System.GC itself. Using these classes properly requires understanding how they interact with the GC. We'll see more on this later.

Unrelated reading: Precedence vs. Associativity Vs. Order.

Footnote

¹ Note that by definition, the simulation extends only to garbage-collected resources. If your program allocates external resources those external resources continue to remain subject to whatever rules apply to them.

• #### How many failure reports does a bug have to get before Windows will fix it?

When a program crashes or hangs, you are given the opportunity to send an error report to Microsoft. This information is collected by the Windows Error Reporting team for analysis. Occasionally, somebody will ask, "How many failures need to be recorded before the bug is fixed? A thousand? Ten thousand? Ten million?"

Each team at Microsoft takes very seriously the failures that come in via Windows Error Reporting. Since failures are not uniformly distributed, and since engineering resources are not infinite, you have to dedicate your limited resources to where they will have the greatest effect. Each failure that is collected and reported is basically a vote for that failure. The more times a failure is reported, the higher up the chart it moves, and the more likely it will make the cut. In practice, 50% of the crashes are caused by 1% of the bugs. Obviously you want to focus on that top 1%.

It's like asking how many votes are necessary to win American Idol. There is no magic number that guarantees victory; it's all relative. As my colleague Paul Betts describes it, "It's like a popularity contest, but of failure."

Depending on the component, it may take only a few hundred reports to make a failure reach the upper part of the failure charts, or it may take hundreds of thousands. And if the failure has been tracked to a third-party plug-in (which is not always obvious in the crash itself and may require analysis to ferret out), then the information is passed along to the plug-in vendor.

What about failures in third-party programs? Sure, send those in, too. The votes are still tallied, and if the company has signed up to access Windows Error Reporting data, they can see which failures in their programs are causing the most problems. Signing up for Windows Error Reporting is a requirement for the Windows 7 software logo program. I've also heard but cannot confirm that part of the deal is that if your failure rate reaches some threshold, your logo certification is at risk of revocation.

If the vendor signed up for Windows Error Reporting but is a slacker and isn't looking at their failures, there's a chance that Microsoft will look at them. Towards the end of the Windows 7 project, the compatibility team looked at the failure data coming from beta releases of Windows 7 to identify the highest-ranked failures in third party programs. The list was then filtered to companies which participated in Windows Error Reporting, and to failures which the vendor had not spent any time investigating. I was one of a group of people asked to study those crashes and basically debug the vendor's program for them.

My TechReady talk basically consisted of going through a few of these investigations. I may clean some of them up for public consumption and post them here, but it's a lot of work because I'd have to write a brand new program that exhibits the bug, force the bug to trigger (often involving race conditions), then debug the resulting crash dump.

I know there is a subculture of people who turn off error reporting, probably out of some sense of paranoia, but these people are ultimately just throwing their vote away. Since they aren't reporting the failures, their feedback doesn't make it back to the failure databases, and their vote for fix this bug never gets reported.

By the way, the method for disabling Windows Error Reporting given in that linked article is probably not the best. You should use the settings in the Windows Error Reporting node in the Group Policy Editor.

I should've seen this coming: Over time, I've discovered that there are a some hot-button topics that derail any article that mentions them. Examples include UAC, DRM, and digital certificate authorities. As a result, I do my best to avoid any mention of them. I didn't mention digital certificate authorities today, but I did link to an article which mentioned them, and now the subject has overrun the comments like kudzu. I don't need to deal with this nonsense, so I'm just going to kill my promised future article that was related to Windows Error Reporting, (I was also planning on converting my talk on debugging application compatibility issues into future articles, but since that's also related to Windows Error Reporting, I'm going to abandon that too.)

• #### Windows 95: It sucks less

Today marks the 15th anniversary of the public release of Windows 95.

During the development of Windows 95, one of the team members attended a Mac conference. And not as a secret agent, either. He proudly wore a Windows 95 team T-shirt as he strolled among the booths.

The rest of us back at the mother ship wished him well and started discussing how we could get access to his dental records so we could identify his remains when they were sent back to us from the conference.

When he returned, we didn't kill a calf in his honor, but we did marvel at his survival skills and asked him how it went.

I got a lot of funny looks. And one guy, upon confirming that I really did work on the Windows 95 project, said to me, "I have to commend you guys on Windows 95 so far. It sucks less."

That backwards compliment tickled the team's funny bone, and it quickly became the unofficial team motto: Windows 95: It sucks less.

• #### What was that story about the WinHelp pen-writing-in-book animation?

The first time you open a WinHelp file, you get this pen-writing-in-book animation while WinHelp does um something which it passes off as preparing Help file for first use or something similarly vague.

I remember a conversation about that animation. The Windows shell team suggested to the author of WinHelp that the program use the shell common animation control to display that animation. After all, it's a short animation and it met the requirements for the animation common control. But the author of WinHelp rejected the notion.

(Pre-emptive "I can't believe I had to write this": This conversation has been exaggerated for effect.)

"Your animation control is so huge and bloated. I can do it much smaller and faster myself. The RLE animation format generates frames by re-rendering the pixels that have changed, which means that at each frame of the animation, a new pen image would be recorded in the AVI file. The pen cycles through three different orientations at each location, there are ten locations on each row, and there are four rows. If I used an RLE animation, that'd be 3 × 10 × 4 = 120 copies of the pen bitmap. Instead, I have just three pen bitmaps, and I manually draw them at the appropriate location for each frame. Something like this:

// NOTE: For simplicity, I'm ignoring the "turn the page" animation
void DrawFrame(int frame)
{
// Calculate our position in the animation
int penframe = frame % 3; // 3 pen images per location
int column = (frame / 3) % 10; // 10 columns per row
int row = (frame / 30) % 4; // 4 rows
int i;
POINT pt;

// Draw the "text" that the pen "wrote" in earlier rows
for (i = 0; i < row; i++) {
DrawTextScribble(i, 0, 9);
}

// Draw the partially-completed row that the pen is on now
DrawTextScribble(row, 0, column);

// Position the pen image so the pen tip hits the "draw" point
GetTextScribblePoint(column, row, &pt);
DrawPenBitmap(penBitmaps[penframe], pt.x - 1, pt.y - 5);
}

"See? In just a few lines of code, I have a complete animation. All I needed was the three pen images and a background bitmap showing a book opened to a blank page. This is way more efficient both in terms of memory and execution time than your stupid animation common control. You shell guys could learn a thing or two about programming."

"Okay, fine, don't need to get all defensive about it. We were just making a suggestion, that's all."

Time passes, and Windows 95 is sent off for translation into the however many languages it is localized for. A message comes in from some of the localization teams. It seems that some locales need to change the animation. For example, the Arabic version of Windows needs the pen to write on the left-hand pages, the pen motion should be right to left, and the pages need to flip from left to right. Perhaps the Japanese translators are okay with the pen motion, but they want the pages to flip from left to right.

The localization team contacted the WinHelp author. "We're trying to change the animation, but we can't find the AVI file in the resources. Can you advise us on how we should localize the animation?"

Unfortunately, the WinHelp author had to tell the localization team that the direction of pen motion, and the locations of the ink marks are hard-coded into the program. Since the product had already passed code lockdown, there was nothing that could be done. WinHelp shipped with a pen that moved in the wrong direction in some locales.

Moral of the story: There's more to software development than programming for performance. Today we learned about localizability.

• #### I challenge you to come up with an even lamer physics pun

The other day, I was in the office kitchenette, and two of my colleagues both named Paul happened to be there getting coffee. I quipped, "Oh no, is this legal? I think it's a violation of the Paul Exclusion Principle."

It was a horrible physics pun, perhaps one of the worst I've made in a long time. My challenge to you is to come up with an even worse one that you've told.

Note: You have to have actually made the pun to an appropriate audience. No fair just making one up for the purpose of the challenge.

• #### How do I get the reference count of a CLR object?

A customer asked the rather enigmatic question (with no context):

Is there a way to get the reference count of an object in .Net?

Thanks,
Bob Smith
Senior Developer
Contoso

The CLR does not maintain reference counts, so there is no reference count to "get". The garbage collector only cares about whether an object has zero references or at least one reference. It doesn't care if there is one, two, twelve, or five hundred—from the point of view of the garbage collector, one is as good as five hundred.

The customer replied,

I am aware of that, yet the mechanism is somehow implemented by the GC...

What I want to know is whether at a certain point there is more then one variable pointing to the same object.

As already noted, the GC does not implement the "count the number of references to this object" algorithm. It only implements the "Is it definitely safe to reclaim the memory for his object?" algorithm. A null garbage collector always answers "No." A tracing collector looks for references, but it only cares whether it found one, not how many it found.

The discussion of "variables pointing to the same objects" is somewhat confused, because you can have references to an object from things other than variables. Parameters to a method contain references, the implicit this is also a reference, and partially-evaluated expressions also contain references. (During execution of the line string s = o.ToString();, at the point immediately after o.ToString() returns and before the result is assigned to s, the string has an active reference but it isn't stored in any variable.) And as we saw earlier, merely storing a reference in a variable doesn't prevent the object from being collected.

It's clear that this person solved half of his problem, and just needs help with the other half, the half that doesn't make any sense. (I like how he immediately weakened his request from "I want the exact reference count" to "I want to know if it is greater than one." Because as we all know, the best way to solve a problem is to reduce it to an even harder problem.)

Another person used some psychic powers to figure out what the real problem is:

If I am reading properly into what you mean, you may want to check out the WeakReference class. This lets you determine whether an object has been collected. Note that you don't get access to a reference count; it's a zero/nonzero thing. If the WeakReference is empty, it means the object has been collected. You don't get a chance to act upon it (as you would if you were the last one holding a reference to it).

The customer explained that he tried WeakReference, but it didn't work. (By withholding this information, the customer made the mistake of not saying what he already tried and why it didn't work.)

Well this is exactly the problem: I instantiate an object and then create a WeakReference to it (global variable).

Then at some point the object is released (set to null, disposed, erased from the face of the earth, you name it) yet if I check the IsAlive property it still returns true.

Only if I explicitly call to GC.Collect(0) or greater before the check it is disposed.

The customer still hasn't let go of the concept of reference counting, since he says that the object is "released". In a garbage-collected system, object are not released; rather, you simply stop referencing them. And disposing of an object still maintains a reference; disposing just invokes the IDisposable.Dispose method.

FileStream fs = new FileStream(fileName);
using (fs) {
...
}

At the end of this code fragment, the FileStream has been disposed, but there is still a reference to it in the fs variable. Mind you, that reference isn't very useful, since there isn't much you can do with a disposed object, Even if you rewrite the fragment as

using (FileStream fs = new FileStream(fileName)) {
...
}

the variable fs still exists after the close-brace; it simply has gone out of scope (i.e., you can't access it any more). Scope is not the same as lifetime. Of course, the optimizer can step in and make the object eligible for collection once the value becomes inaccessible, but there is no requirement that this optimization be done.

The fact that the IsAlive property says true even after all known references have been destroyed is also no surprise. The environment does not check whether an object's last reference has been made inaccessible every time a reference changes. One of the major performance benefits of garbage collected systems comes from the de-amortization of object lifetime determination. Instead of maintaining lifetime information about an object continuously (spending a penny each time a reference is created or destroyed), it saves up those pennies and splurges on a few dollars every so often. The calculated risk (which usually pays off) is that the rate of penny-saving makes up for the occasional splurges.

It does mean that between the splurges, the garbage collector does not know whether an object has outstanding references or not. It doesn't find out until it does a collection.

The null garbage collector takes this approach to an extreme by simply hoarding pennies and never spending them. It saves a lot of money but consumes a lot of memory. The other extreme (common in unmanaged environments) is to spend the pennies as soon as possible. It spends a lot of money but reduces memory usage to the absolute minimum. The designers of a garbage collector work to find the right balance between these two extremes, saving money overall while still keeping memory usage at a reasonable level.

The customer appears to have misinterpreted what the IsAlive property means. The property doesn't say whether there are any references to the object. It says whether the object has been garbage collected. Since the garbage collector can run at any time, there is nothing meaningful you can conclude if IsAlive returns true, since it can transition from alive to dead while you're talking about it. On the other hand, once it's dead, it stays dead; it is valid to take action when IsAlive is false. (Note that there are two types of WeakReference; the difference is when they issue the death certificate.)

The name IsAlive for the property could be viewed as misleading if you just look at the property name without reading the accompanying documentation. Perhaps a more accurate (but much clumsier) name would have been HasNotBeenCollected. The theory is, presumably, that if you're using an advanced class like WeakReference, which works "at the GC level", you need to understand the GC.

The behavior the customer is seeing is correct. The odds that the garbage collector has run between annihilating the last live reference and checking the IsAlive property is pretty low, so when you ask whether the object has been collected, the answer will be No. Of course, forcing a collection will cause the garbage collector to run, and that's what does the collection and sets IsAlive to false. Mind you, forcing the collection to take place messes up the careful penny-pinching the garbage collector has been performing. You forced it to pay for a collection before it had finished saving up for it, putting the garbage collector in debt. (Is there a garbage collector debt collector?) And the effect of a garbage collector going into debt is that your program runs slower than it would have if you had let the collector spend its money on its own terms.

Note also that forcing a generation-zero collection does not guarantee that the object in question will be collected: It may have been promoted into a higher generation. (Generational garbage collection takes advantage of typical real-world object lifetime profiles by spending only fifty cents on a partial collection rather than a whole dollar on a full collection. As a rough guide, the cost of a collection is proportional to the number of live object scanned, so the most efficient collections are those which find mostly dead objects.) Forcing an early generation-zero collection messes up the careful balance between cheap-but-partial collections and expensive-and-thorough collections, causing objects to get promoted into higher generations before they really deserve it.

Okay, that was a long discussion of a short email thread. Maybe tomorrow I'll do a better job of keeping things short.

Bonus chatter: In addition to the WeakReference class, there is also the GCHandle structure.

Bonus reading: Maoni's WebLog goes into lots of detail on the internals of the CLR garbage collector. Doug Stewart created this handy index.

• #### Be careful that your splash screen doesn't squander the foreground love

Commenter Erbi has a program which creates a splash screen on a background thread while the main thread initializes. "I create and then destroy this splash screen window just before creating and displaying the main window." The problem is that the main window fails to obtain foreground activation. Commenting out the code that creates the splash screen fixes the problem, but then there isn't a splash screen any more (obviously). "Is there an explanation for this behavior?"

This behavior is explained by two earlier blog posts, plus a PDC talk. The first blog post came out years before this question was asked: The correct order for disabling and enabling windows. Destroying a window is a rather extreme case of disabling it, but the effect is the same. When you destroy the splash screen, foreground activation needs to move to some other window, and since your main window isn't around to inherit it, foreground activation leaves your program. When the main window appears, it's too late.

The PDC talk came next, followed shortly thereafter by a blog post version of the same talk. As marketing folks like to remind you, "You get only one chance to make a first impression." Similarly, you get only one chance to use your foreground activation permission, and you decided to blow it on a splash screen. That's fine as far as it goes, but if you want to transfer that permission to another window, you have to manage it yourself. The recommended way is to establish an owner/owned relationship between them; that's the case that the "disabling and enabling windows" article focuses on.

• #### When do I need to use GC.KeepAlive?

Finalization is the crazy wildcard in garbage collection. It operates "behind the GC", running after the GC has declared an object dead. Think about it: Finalizers run on objects that have no active references. How can this be a reference to an object that has no references? That's just crazy-talk!

Finalizers are a Ouija board, permitting dead objects to operate "from beyond the grave" and affect live objects. As a result, when finalizers are involved, there is a lot of creepy spooky juju going on, and you need to tread very carefully, or your soul will become cursed.

Let's step back and look at a different problem first. Consider this class which doesn't do anything interesting but works well enough for demonstration purposes:

class Sample1 {
public Sample1(string file) : sr(new StreamReader(file)) { }
public void Close() { sr.Close(); }
public string NextLine() { return sr.ReadLine(); }
}

What happens if one thread calls Sample1.NextLine() and another thread calls Sample1.Close()? If the NextLine() call wins the race, then you have a stream closed while it is in the middle of its ReadLine method. Probably not good. If the Close() call wins the race, then when the NextLine() call is made, you end up reading from a closed stream. Definitely not good. Finally, if the NextLine() call runs to completion before the Close(), then the line is successfully read before the stream is closed.

Having this race condition is clearly an unwanted state of affairs since the result is unpredictable.

Now let's change the Close() method to a finalizer.

class Sample2 {
public Sample2(string file) : sr(new StreamReader(file)) { }
~Sample2() { sr.Close(); }
public string NextLine() { return sr.ReadLine(); }
}

Remember that we learned that an object becomes eligible for garbage collection when there are no active references to it, and that it can happen even while a method on the object is still active. Consider this function:

string FirstLine(string fileName) {
Sample2 s = new Sample2(fileName);
return s.NextLine();
}

We learned that the Sample2 object becomes eligible for collection during the execution of NextLine(). Suppose that the garbage collector runs and collects the object while NextLine is still running. This could happen if ReadLine takes a long time, say, because the hard drive needs to spin up or there is a network hiccup; or it could happen just because it's not your lucky day and the garbage collector ran at just the wrong moment. Since this object has a finalizer, the finalizer runs before the memory is discarded, and the finalizer closes the StreamReader.

Boom, we just hit the race condition we considered when we looked at Sample1: The stream was closed while it was being read from. The garbage collector is a rogue thread that closes the stream at a bad time. The problem occurs because the garbage collector doesn't know that the finalizer is going to make changes to other objects.

Classically speaking, there are three conditions which in combination lead to this problem:

1. Containment: An entity a retains a reference to another entity b.
2. Incomplete encapsulation: The entity b is visible to an entity outside a.
3. Propagation of destructive effect: Some operation performed on entity a has an effect on entity b which alters its proper usage (usually by rendering it useless).

The first condition (containment) is something you do without a second's thought. If you look at any class, there's a very high chance that it has, among its fields, a reference to another object.

The second condition (incomplete encapsulation) is also a common pattern. In particular, if b is an object with methods, it will be visible to itself.

The third condition (propagation of destructive effect) is the tricky one. If an operation on entity a has a damaging effect on entity b, the code must be careful not to damage it while it's still being used. This is something you usually take care of explicitly, since you're the one who wrote the code that calls the destructive method.

Unless the destructive method is a finalizer.

If the destructive method is a finalizer, then you do not have complete control over when it will run. And it is one of the fundamental laws of the universe that events will occur at the worst possible time.

Enter GC.KeepAlive(). The purpose of GC.KeepAlive() is to force the garbage collector to treat the object as still live, thereby preventing it from being collected, and thereby preventing the finalizer from running prematurely.

(Here's the money sentence.) You need to use GC.KeepAlive when the finalizer for an object has a destructive effect on a contained object.

The problem is that it's not always clear which objects have finalizers which have destructive effect on a contained object. There are some cases where you can suspect this is happening due to the nature of the object itself. For example, if the object manages something external to the CLR, then its finalizer will probably destroy the external object. But there can be other cases where the need for GC.KeepAlive is not obvious.

A much cleaner solution than using GC.KeepAlive is to use the IDisposable interface, formalized by the using keyword. Everybody knows that the using keyword ensures that the object being used is disposed at the end of the block. But it's also the case (and it is this behavior that is important today) that the using keyword also keeps the object alive until the end of the block. (Why? Because the object needs to be alive so that we can call Dispose on it!)

This is one of the reasons I don't like finalizers. Since they operate underneath the GC, they undermine many principles of garbage collected systems. (See also resurrection.) As we saw earlier, a correctly-written program cannot rely on side effects of a finalizer, so in theory all finalizers could be nop'd out without affecting correctness.

The garbage collector purist in me also doesn't like finalizers because they prevent the running time of a garbage collector to be proportional to the amount of live data, like say in a classic two-space collector. (There is also a small constant associated with the amount of dead data, which means that the overall complexity is proportional to the amount of total data.)

If I ruled the world, I would decree that the only thing you can do in a finalizer is perform some tests to ensure that all the associated external resources have already been explicitly released, and if not, raise a fatal exception: System.Exception.ResourceLeak.

• #### Everybody thinks about CLR objects the wrong way (well not everybody)

Many people responded to Everybody thinks about garbage collection the wrong way by proposing variations on auto-disposal based on scope:

What these people fail to recognize is that they are dealing with object references, not objects. (I'm restricting the discussion to reference types, naturally.) In C++, you can put an object in a local variable. In the CLR, you can only put an object reference in a local variable.

For those who think in terms of C++, imagine if it were impossible to declare instances of C++ classes as local variables on the stack. Instead, you had to declare a local variable that was a pointer to your C++ class, and put the object in the pointer.

C#C++
void Function(OtherClass o)
{
// No longer possible to declare objects
// with automatic storage duration
Color c(0,0,0);
Brush b(c);
o.SetBackground(b);
}
void Function(OtherClass o)
{
Color c = new Color(0,0,0);
Brush b = new Brush(c);
o.SetBackground(b);
}
void Function(OtherClass* o)
{
Color* c = new Color(0,0,0);
Brush* b = new Brush(c);
o->SetBackground(b);
}

This world where you can only use pointers to refer to objects is the world of the CLR.

In the CLR, objects never go out of scope because objects don't have scope.¹ Object references have scope. Objects are alive from the point of construction to the point that the last reference goes out of scope or is otherwise destroyed.

If objects were auto-disposed when references went out of scope, you'd have all sorts of problems. I will use C++ notation instead of CLR notation to emphasize that we are working with references, not objects. (I can't use actual C++ references since you cannot change the referent of a C++ reference, something that is permitted by the CLR.)

C#C++
void Function(OtherClass o)
{
Color c = new Color(0,0,0);
Brush b = new Brush(c);
Brush b2 = b;
o.SetBackground(b2);

}
void Function(OtherClass* o)
{
Color* c = new Color(0,0,0);
Brush* b = new Brush(c);
Brush* b2 = b;
o->SetBackground(b2);
// automatic disposal when variables go out of scope
dispose b2;
dispose b;
dispose c;
dispose o;
}

Oops, we just double-disposed the Brush object and probably prematurely disposed the OtherClass object. Fortunately, disposal is idempotent, so the double-disposal is harmless (assuming you actually meant disposal and not destruction). The introduction of b2 was artificial in this example, but you can imagine b2 being, say, the leftover value in a variable at the end of a loop, in which case we just accidentally disposed the last object in an array.

Let's say there's some attribute you can put on a local variable or parameter to say that you don't want it auto-disposed on scope exit.

C#C++
void Function([NoAutoDispose] OtherClass o)
{
Color c = new Color(0,0,0);
Brush b = new Brush(c);
[NoAutoDispose] Brush b2 = b;
o.SetBackground(b2);

}
void Function([NoAutoDispose] OtherClass* o)
{
Color* c = new Color(0,0,0);
Brush* b = new Brush(c);
[NoAutoDispose] Brush* b2 = b;
o->SetBackground(b2);
// automatic disposal when variables go out of scope
dispose b;
dispose c;
}

Okay, that looks good. We disposed the Brush object exactly once and didn't prematurely dispose the OtherClass object that we received as a parameter. (Maybe we could make [NoAutoDispose] the default for parameters to save people a lot of typing.) We're good, right?

Let's do some trivial code cleanup, like inlining the Color parameter.

C#C++
void Function([NoAutoDispose] OtherClass o)
{
Brush b = new Brush(new Color(0,0,0));
[NoAutoDispose] Brush b2 = b;
o.SetBackground(b2);

}
void Function([NoAutoDispose] OtherClass* o)
{
Brush* b = new Brush(new Color(0,0,0));
[NoAutoDispose] Brush* b2 = b;
o->SetBackground(b2);
// automatic disposal when variables go out of scope
dispose b;
}

Whoa, we just introduced a semantic change by what seemed like a harmless transformation: The Color object is no longer auto-disposed. This is even more insidious than the scope of a variable affecting its treatment by anonymous closures, for introduction of temporary variables to break up a complex expression (or removal of one-time temporary variables) are common transformations that people expect to be harmless, especially since many language transformations are expressed in terms of temporary variables. Now you have to remember to tag all of your temporary variables with [NoAutoDospose].

Wait, we're not done yet. What does SetBackground do?

C#C++
void OtherClass.SetBackground([NoAutoDispose] Brush b)
{
this.background = b;
}
void OtherClass::SetBackground([NoAutoDispose] Brush* b)
{
this->background = b;
}

Oops, there is still a reference to that Brush in the o.background member. We disposed an object while there were still outstanding references to it. Now when the OtherClass object tries to use the reference, it will find itself operating on a disposed object.

Working backward, this means that we should have put a [NoAutoDispose] attribute on the b variable. At this point, it's six of one, a half dozen of the other. Either you put using around all the things that you want auto-disposed or you put [NoAutoDispose] on all the things that you don't.²

The C++ solution to this problem is to use something like shared_ptr and reference-counted objects, with the assistance of weak_ptr to avoid reference cycles, and being very selective about which objects are allocated with automatic storage duration. Sure, you could try to bring this model of programming to the CLR, but now you're just trying to pick all the cheese off your cheeseburger and intentionally going against the automatic memory management design principles of the CLR.

I was sort of assuming that since you're here for CLR Week, you're one of those people who actively chose to use the CLR and want to use it in the manner in which it was intended, rather than somebody who wants it to work like C++. If you want C++, you know where to find it.

Footnote

¹ Or at least don't have scope in the sense we're discussing here.

² As for an attribute for specific classes to have auto-dispose behavior, that works only if all references to auto-dispose objects are in the context of a create/dispose pattern. References to auto-dispose objects outside of the create/dispose pattern would need to be tagged with the [NoAutoDispose] attribute.

[AutoDispose] class Stream { ... };

Stream MyClass.GetSaveStream()
{
[NoAutoDispose] Stream stm;
if (saveToFile) {
stm = ...;
} else {
stm = ...;
}
return stm;
}

void MyClass Save()
{
// NB! do not combine into one line
Stream stm = GetSaveStream();
SaveToStream(stm);
}

• #### Why does the primary monitor have (0,0) as its upper left coordinate?

By definition, the primary monitor is the monitor that has (0,0) as its upper left corner. Why can't the primary monitor be positioned somewhere else?

Well, sure you could do that, but then you'd have to invent a new name for the monitor whose upper left corner is at (0,0), and then you're back where you started.

In other words, it's just a name. You could ask, "Why can't starboard be on the left-hand side of the boat?" Well, sure you could do that, but then you'd have to come up with a new name for the right-hand side of the boat, and then things are pretty much the same as they were, just with different names.

Perhaps a more descriptive (but clumsier) name for the primary monitor would be the backward-compatibility monitor (for applications which do not support multiple monitors), because that's what the primary monitor is. If an application is not multiple-monitor aware, then any time it asks for properties of "the" monitor, it gets information about the backward-compatibility monitor. A call to GetSystemMetrics(SM_CXSCREEN) gives the width of the backward-compatibility monitor, GetSystemMetrics(SM_CYMAXIMIZED) gives the height of a window maximized on the backward-compatibility monitor, and positioning a window at (0,0) puts it at the upper left corner of the backward-compatibility monitor.

The window manager still respects window coordinates passed to functions like CreateWindow or SetWindowPos. If you pass coordinates that are on a secondary monitor—oops—a monitor different from the backward-compatibility monitor, then the window manager will happily put the window there. These coordinates might be the result of a program that is multiple-monitor aware, or possibly merely from a program which is multiple-monitor agnostic.

Multiple-monitor agnosticism is a term I just made up which refers to programs which might not explicitly support multiple monitors, but at least were open to the possibility of multiple monitors by not making assumptions about the number of monitors but instead using functions like RectVisible to determine what the visible portions of the screen are. These techniques were hot topics many years ago when you wanted to write a program that ran both on single-monitor-only versions of Windows as well as multiple-monitor versions of windows; nowadays there are rather old-fashioned, like coming up with mnemonics for all your friends' telephone numbers so you didn't have to keep looking them up. (Today, you just go ahead and call the multiple monitor functions and use the address book function in your mobile phone to remember your friends' phone numbers.)

It is not the case that the primary monitor is the applications show up here first monitor. As noted earlier, applications show up on whatever monitor they ask for, whether they asked for it explicitly (hunting around for a monitor and using it) or implicitly (restoring to the same coordinates they were on when they were last run).

Of course, programs which pass CW_USEDEFAULT to the CreateWindow function explicitly abdicated the choice of the window position and therefore the monitor. In that case, the window manager tries to guess an appropriate monitor. If the new window has a parent or owner, then it is placed on the same monitor as that parent or owner; otherwise, the window manager just puts the window on the backward-compatible monitor, for lack of a better idea.

Page 1 of 3 (29 items) 123


text:
How can we model intrinsic curvature?

+ 0 like - 0 dislike
77 views

Can it only be done in Euclidean space? Doesn't Euclidean space only model extrinsic curvature?

This post imported from StackExchange Physics at 2014-03-22 16:54 (UCT), posted by SE-user Ocsis2

retagged Mar 25, 2014

+ 4 like - 0 dislike

I'm not quite sure what you mean by the term "model" in this context, but:

If a space is a Euclidean space, in the sense that it has a Euclidean metric, then its Levi Civita connection (the connection compatible with its metric) has no intrinsic curvature (for example a flat plane is like this). However, it may be given some extrinsic curvature by means of an embedding into a higher dimensional space (the flat plane may be rolled up into a cylinder in $\mathbb{R}^3$).

But if you were a two dimensional organism living on the cylinder, you couldn't detect this extrinsic curvature by locally measuring angles and distances.

This post imported from StackExchange Physics at 2014-03-22 16:54 (UCT), posted by SE-user twistor59
answered Apr 11, 2012 by (2,500 points)
Very clear. How can one relate both metrics?

This post imported from StackExchange Physics at 2014-03-22 16:54 (UCT), posted by SE-user phoenix
+ 0 like - 0 dislike

No, Euclidian space is not necessary. You can "model" intrinsic curvature using the beautiful language of Riemannian geometry, whose great triumph was formulating a vocabulary that lets you talk about the curvature of a space without making reference to an extrinsic space in which the curved space is embedded: hence the term intrinsic.

This is crucial to general relativity, since embedding a curved 4-space in flat Euclidean space requires that the Euclidean space be ten-dimensional, and dealing with that embedding would suck.

This post imported from StackExchange Physics at 2014-03-22 16:54 (UCT), posted by SE-user Rory
answered Apr 12, 2012 by (0 points)

 Please use answers only to (at least partly) answer questions. To comment, discuss, or ask for clarification, leave a comment instead. To mask links under text, please type your text, highlight it, and click the "link" button. You can then enter your link URL. Please consult the FAQ for as to how to format your post. This is the answer box; if you want to write a comment instead, please use the 'add comment' button. Live preview (may slow down editor)   Preview Your name to display (optional): Email me at this address if my answer is selected or commented on: Privacy: Your email address will only be used for sending these notifications. Anti-spam verification: If you are a human please identify the position of the character covered by the symbol $\varnothing$ in the following word:p$\hbar$ysicsOver$\varnothing$lowThen drag the red bullet below over the corresponding character of our banner. When you drop it there, the bullet changes to green (on slow internet connections after a few seconds). To avoid this verification in future, please log in or register.

format: plain


text: 1 $\begingroup$ Closed. Google metamerism to learn more. Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. But when I use the transfer matrix cited on wikipedia (https://en.wikipedia.org/wiki/SRGB) I find: $$xyz = (0.145945, 0.045217, 0.808838) \rightarrow RGB = (0.000155,-0.023021, 0.854036)$$ A simple tool to convert a wavelength in nm to an RGB, hexadecimal or HSL colour. rev 2020.11.24.38066, The best answers are voted up and rise to the top, Physics Stack Exchange works best with JavaScript enabled, Start here for a quick overview of the site, Detailed answers to any questions you might have, Discuss the workings and policies of this site, Learn more about Stack Overflow the company, Learn more about hiring developers or posting ads with us, $$xyz = (0.145945, 0.045217, 0.808838) \rightarrow RGB = (0.000155,-0.023021, 0.854036)$$, FWIW: The colors of many (most?) What is the best way to remove 100% of a software that is not yet installed? sRGB does not define wavelengths, but the XYZ coordinates of the primaries. what is the correct way to perform steps 3-7? Is a software open source if its source code is published by its copyright owner but cannot be used without a commercial license. (sRGB.xlsm의 "sRGB"시트에서 발견할 수 있을 것임) 위에서 사용한 데이터는 5nm 간격의 파장에 대한 데이터이다. I don't know how to convert $xyz$ chromaticity coordinates in sRGB. Most of the cameras use sRGB which has a well defined nonlinear function for converting the linear R,G,B values to the values stored in pixels. Physics Light Colour Over the course of millions of years, the human eye has evolved to detect light in the range 380—780nm, a portion of the electromagnetic spectrum known as visible light , … Unable to complete the action because of changes made to the page. Choose a web site to get translated content where available and see local events and offers. Universally. This is general color science, not something specific to MATLAB. Opportunities for recent engineering grads. https://www.mathworks.com/matlabcentral/answers/240430-rgb-to-wavelength-is-it-possible#answer_191518, https://www.mathworks.com/matlabcentral/answers/240430-rgb-to-wavelength-is-it-possible#comment_308361, https://www.mathworks.com/matlabcentral/answers/240430-rgb-to-wavelength-is-it-possible#comment_308370, https://www.mathworks.com/matlabcentral/answers/240430-rgb-to-wavelength-is-it-possible#comment_308371, https://www.mathworks.com/matlabcentral/answers/240430-rgb-to-wavelength-is-it-possible#comment_308505. Also, surfers like to ride on them. Why did MacOS Classic choose the colon as a path separator? So for light that we would consider "blue", there is going to be significant excitation of the green cones as well, nearly as much as the blue cones at those wavelengths; and likewise, the blue cones are going to be excited by areas that you would consider "green". Why did Pilate punish Jesus in Luke 23:16? the "color" of that object as it would appear to the eye. There are several color matching functions, available as tables or as analytic approximations (suggested by @Tarc and @Haochen Xie). The accuracy is going to depend a lot on the illuminating frequency and upon whether you choose the right model (formulary). If you look in the above link at the second newsreader thread you will see that William linked to, http://www.mathworks.com/matlabcentral/fileexchange/7021-spectral-and-xyz-color-functions. Accelerating the pace of engineering and science. How do we get to know the total mass of an atmosphere? say "even if it was a slight approximation"... Like I said in the link Walter referred you to, Some arbitrary RGB does not necessarily map to one single pure wavelength. site design / logo © 2020 Stack Exchange Inc; user contributions licensed under cc by-sa. Different degrees of freedom with RGB, CMYK and Frequency, Wavelength of light in a gravitational field, Scaling of the CIE RGB color matching functions, Generic word for firearms with long barrels. Is it too late for me to get into competitive chess? RGB Model: Adobe RGB(1998) Apple RGB Best RGB Beta RGB Bruce RGB CIE RGB ColorMatch RGB Don RGB 4 ECI RGB v2 Ekta Space PS5 NTSC RGB PAL/SECAM RGB ProPhoto RGB SMPTE-C RGB sRGB Wide Gamut RGB Gamma: sRGB_detailed.xlsm에 그 값을 작성해봤다. This is general color science, not something specific to MATLAB. Presume that I have a spectrum as a function of wavelength (an example being the blackbody spectrum): I want to convert that to a single RGB color to display on-screen, i.e. By using our site, you acknowledge that you have read and understand our Cookie Policy, Privacy Policy, and our Terms of Service. MathWorks is the leading developer of mathematical computing software for engineers and scientists. Famous grandmaster games of "torturous" winning or flaunting out of arrogance? the author takes: $$xyz = (0.145945, 0.045217, 0.808838) \rightarrow RGB = (1.47450, -178.21694, 345.59392)$$. ). What is a good way to convert a RGB pixel to a wavelength ? Tables are best if you need a smooth preсise result. First, note that there are many RGB colour systems. It only takes a minute to sign up. Is conduit required when running a short distance to an adjacent 60 amp subpanel? Reload the page to see its updated state. Viewed 51 times 2. A single RGB triplet of values might be arrived at from a whole broad spectrum of wavelengths, not just one wavelength. Stack Exchange network consists of 176 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.


text:
# How do you find the midpoint of A (1,3) and Q(7,9)?

Mar 19, 2018

$\left(4 , 6\right)$

#### Explanation:

The midpoint of two coordinates is the mean of the coordinates

for $\left({x}_{1} , {y}_{1}\right) , \left({x}_{2} , {y}_{2}\right)$

the midpoint is

$M \left(\frac{{x}_{1} + {x}_{2}}{2} , \frac{{y}_{1} + {y}_{2}}{2}\right)$

we have

A(1,3);B(7.9)

$\implies M \left(\frac{1 + 7}{2} , \frac{3 + 9}{2}\right)$

$M \left(\frac{8}{2} , \frac{12}{2}\right)$

$M \left(4 , 6\right)$


text:
# Math 310: Congruences Using SageMath xgcd()

## 0. Otherview

This interactive worksheet looks at solving congruences with the help of the idea that a greatest common divisor of two integers can be written as a linear combination of the two integers. It also helps to have the Extended Euclidean Algorithm available using the SageMath xgcd().

### Using SageMath Cells

You will find SageMath Cells in this worksheet. Some include code that demonstrates SageMath functions and syntax. Some that generate the constants ($$a, b, p, q$$) that will setup the questions you will answer.

For each of the 4 SageMath Cells in this section:

• Read the comment above the Cell.
• Click the Evaluate button
• Observe the output in the output box.
• Explain the Cell results to your notebook or another person at your table.

1. Notice the output: By default, SageMath only echos the value of the last line.

2. You can use print statements to get more feedback.

3. xgcd() and mod() are two functions you can use.

4. Note: The results of each executed cell are passed on to the cells below. The results are lost every time you reload the web page.

### Take notes as you work through these the two questions

Everything you enter will be lost when you reload this web page. You should take notes as you go along.

## 1. Solving a congruence

Select a random integer $$a$$ in the range of 1000 to 2000. Use $$a$$ to pick the $$a^{th}$$ prime number

### Question 1

Use the xgcd() function to solve the congruence: $a \cdot x \equiv 1 \bmod p$ using the values of $$a$$ and $$p$$ selected above.

Here are two Cells to use for code to answer question 1:

Use this SageMath Cell to demonstrate that your numeric answer is correct.

## 2. Solving a pair of simultaneous congruences

We have $$a$$ and $$p$$ from question 1, so get $$b$$ and $$q$$ the same way.

### Question 2

Solve:

$$x \equiv a \bmod p \\ x \equiv b \bmod q$$

using the values of $$a, b, p$$ and $$q$$ selected above.

#### Notebook Comment For Question 2

How do you know there will be a solution? Write the complete question and your reasoning in your notebook.

Here are two Cells to use for code to answer question 2:

Use this SageMath Cell to demonstrate that your numeric answer is correct.


text:
1. ## Application of differentiation

A baseball diamond is a square with side 90 ft. A batter his the balls and runs toward first base with a speed of 24ft/s.
a. At what rate is his distance from the second base decreasing when he is halfway to first base?
b. At what rate is his distance from third base increasing at the same moment.

2. Originally Posted by camherokid
A baseball diamond is a square with side 90 ft. A batter his the balls and runs toward first base with a speed of 24ft/s.
a. At what rate is his distance from the second base decreasing when he is halfway to first base?
b. At what rate is his distance from third base increasing at the same moment.
a) I'm sure i've seen this problem before, but i can't find it now, so let's reinvent the wheel.

As with all related rates problems, you want to begin by drawing a diagram to see what's going on (I see you have one already). I have attached one to show you how I am interpreting the problem. Then you want to write down what you know and don't know. I know the value for ds/dt but not dD/dt.

Let the distance of the batter from 1st base as he runs be s. Let distance he is away from the second base be D. The rate at which the batter is running towards 1st, ds/dt, is equal to - 24 feet/sec (we make this negative becuase the distance between the runner and 1st is decreasing). Also notice that we have s and D changing, and not the distance between 1st and 2nd base, so we can keep the latter distance at a constant 90 feet.

From the diagram, we realize that we have a right angled triangle connecting the runner, 2nd and 1st base. So our main formula will be Pythagoras' formula. Here goes.

D^2 = 90^2 + s^2
differentiate implicitly, we obtain:

2D dD/dt = 2s ds/dt
=> dD/dt = (2s ds/dt)/2D
The above is the formula we will be using, but we have to make sure that the only unknown in it is what we want to find, dD/dt.

By pythagoras again, we realize, when the runner is halfway to 1st, he is 45 feet away from 1st. So we can find D, by D^2 = 45^2 + 90^2 => D = 100.62 feet.

Now we know everything we need.
Using s = 45, D = 100.62, ds/dt = - 24, we get:

dD/dt = [2(45)(-24)]/[2(100.62)]
= - 10.73 feet per sec

b) Similar to how I constructed part a) we do part b).
Skipping the details, we have

here, x = 45 ft, E = 100.62, dx/dt = 24 ft/s ...this is positive now since the distance between the runner and home base is increasing

so now
E^2 = x^2 + 90^2
=> 2E dE/dt = 2x dx/dt
=> dE/dt = (2x dx/dt)/2E
=> dE/dt = [2(45)(24)]/[2(100.62)]
= 10.73 feet per sec

3. sorry, here's the diagram i meant to post


text:
### #include

Syntax:

`    #include filename`

Explanation:

`#include` tells Great Cow BASIC to open up another file, read all of the subroutines and constants from it, and then copy them into the current program.

There are two forms of include; absolute and relative.

Absolute is used to refer to files in the `..\GreatCowBASIC\include` directory. The name of the file is specified in between < and > symbols. For instance, to include the file `srf04.h`, the directive is:

`    #include <srf04.h>`

Relative is used to read files in the same folder as the currently selected program. Filenames are given enclosed in quotation marks, such as where `mycode.h` is the name of the file that is to be read.

`    #include "mycode.h"`

NOTES: It is not essential that the include file name ends in .h - the important thing is that the name given to Great Cow BASIC is the exact name of the file to be included.

Those who are familiar with `#include` in assembly or C should bear in mind that `#include` in Great Cow BASIC works differently to `#include` in most other languages - code is not inserted at the location of the `#include`, but rather at the end of the current program.


text:
1. ## differential modelling

Can someone pls help me out with this question.
As water floes out from a straight cylindrical vessel, the rate of change of the height of the free surface level is directly proportional to the square root of the height.It os observed that the height at t=o is h02.25m and at t=90s h=1.75m.When will be height be h=1.25m

2. Originally Posted by lakuzy100
Can someone pls help me out with this question.
As water floes out from a straight cylindrical vessel, the rate of change of the height of the free surface level is directly proportional to the square root of the height.It os observed that the height at t=o is h02.25m and at t=90s h=1.75m.When will be height be h=1.25m
The statement

the rate of change of the height of the free surface level is directly proportional to the square root of the height
tells us how to set up the differential equation.

It tells us that the rate of change of the height $\left(\frac{\,dh}{\,dt}\right)$ is directly proportional to the square root of the height $\left(\sqrt{h}\right)$

Thus, our DE is $\frac{\,dh}{\,dt}=k\sqrt{h}$, where $k$ is some constant of proportionality.

To solve, apply the separation of variables technique:

$\frac{\,dh}{\,dt}=k\sqrt{h}\implies \frac{\,dh}{\sqrt{h}}=k\,dt$

Integrating both sides, we see that

$2\sqrt{h}=kt+C\implies h=\left(\tfrac{1}{2}kt+C\right)^2$

Use the first condition to find C.

Then use the second condition to find k.

Finally, find the time it takes to reach a height of 1.25.

Can you take it from here?

--Chris


text:
# LieDerivation \\ List -- formal application of a derivation to every element in a list

## Synopsis

• Operator: \\
• Usage:
y = d\\x
• Inputs:
• d, an instance of the type LieDerivation,
• x, a list, the elements in $x$ belong to the source of $d$
• Outputs:
• y, a list, the elements in $y$ are the formal application of $d$ to the elements in $x$

## Description

 i1 : L = lieAlgebra{a,b}/{a a a b,b b b a} o1 = L o1 : LieAlgebra i2 : d = euler L o2 = d o2 : LieDerivation i3 : d\\basis(5,L) o3 = {(a b a b a) + (a b a b a) + (a b a b a) + (a b a b a) + (a b a b a), (b ------------------------------------------------------------------------ b a b a) + (b b a b a) + (b b a b a) + (b b a b a) + (b b a b a)} o3 : List i4 : d\basis(5,L) o4 = {5 (a b a b a), 5 (b b a b a)} o4 : List


text:
# 3.3 Counting with Bijections

## Counting Functions

How many total functions are there from set $$A$$ to set $$B$$ if $$|A|=3$$ and $$|B|=7$$? Please enter your answer in the form x^y.

Exercise 1

Say $$A = \{a_1, a_2, a_3 \}$$. There is a bijection between total functions from $$A$$ to $$B$$ and length-3 vectors of elements of $$B$$. In this bijection, a given total function $$f$$ corresponds to the vector $$(f(a_1), f(a_2), f(a_3)) \in B^3$$. Hence, by the product rule, $$|B^3| = 7^3$$.


text:
# 1. Memoryless Distributions¶

In addition to what’s in Anaconda, this lecture will need the following libraries:

!pip install quantecon

Requirement already satisfied: quantecon in /usr/share/miniconda3/envs/quantecon/lib/python3.8/site-packages (0.5.2)
Requirement already satisfied: numpy in /usr/share/miniconda3/envs/quantecon/lib/python3.8/site-packages (from quantecon) (1.20.3)
Requirement already satisfied: sympy in /usr/share/miniconda3/envs/quantecon/lib/python3.8/site-packages (from quantecon) (1.9)
Requirement already satisfied: scipy>=1.0.0 in /usr/share/miniconda3/envs/quantecon/lib/python3.8/site-packages (from quantecon) (1.7.1)
Requirement already satisfied: numba>=0.38 in /usr/share/miniconda3/envs/quantecon/lib/python3.8/site-packages (from quantecon) (0.54.1)
Requirement already satisfied: requests in /usr/share/miniconda3/envs/quantecon/lib/python3.8/site-packages (from quantecon) (2.26.0)
Requirement already satisfied: setuptools in /usr/share/miniconda3/envs/quantecon/lib/python3.8/site-packages (from numba>=0.38->quantecon) (58.0.4)
Requirement already satisfied: llvmlite<0.38,>=0.37.0rc1 in /usr/share/miniconda3/envs/quantecon/lib/python3.8/site-packages (from numba>=0.38->quantecon) (0.37.0)

Requirement already satisfied: idna<4,>=2.5 in /usr/share/miniconda3/envs/quantecon/lib/python3.8/site-packages (from requests->quantecon) (3.2)
Requirement already satisfied: certifi>=2017.4.17 in /usr/share/miniconda3/envs/quantecon/lib/python3.8/site-packages (from requests->quantecon) (2021.10.8)
Requirement already satisfied: urllib3<1.27,>=1.21.1 in /usr/share/miniconda3/envs/quantecon/lib/python3.8/site-packages (from requests->quantecon) (1.26.7)
Requirement already satisfied: charset-normalizer~=2.0.0 in /usr/share/miniconda3/envs/quantecon/lib/python3.8/site-packages (from requests->quantecon) (2.0.4)
Requirement already satisfied: mpmath>=0.19 in /usr/share/miniconda3/envs/quantecon/lib/python3.8/site-packages (from sympy->quantecon) (1.2.1)

## 1.1. Overview¶

Markov processes are, by definition, forgetful.

In particular, for any Markov processes, the distribution over future outcomes depends only on the current state, rather than the entire history.

In the case of continuous time Markov chains, which jump between discrete states, this requires that the amount of elapsed time since the last jump is not helpful in predicting the timing of the next jump.

In other words, the jump times are “memoryless”.

It is remarkable that the only distribution on $$\RR_+$$ with this property is the exponential distribution.

Similarly, the only memoryless distribution on $$\ZZ_+$$ is the geometric distribution.

This lecture tries to clarify these ideas.

We will use the following imports:

import numpy as np
import matplotlib.pyplot as plt
import quantecon as qe
from numba import njit
from scipy.special import factorial, binom

## 1.2. The Geometric Distribution¶

Consider betting on a roulette wheel and suppose that red has come up four times in a row.

Since five reds in a row is an unlikely event, many people instinctively feel that black is more likely on the fifth spin — “Surely black will come up this time!”

But rational thought tells us such instincts are wrong: the four previous reds make no difference to the outcome of the next spin.

(Many casinos offer an unlimited supply of free alcoholic beverages in order to discourage this kind of rational analysis.)

A mathematical restatement of this phenomenon is: the geometric distribution is memoryless.

### 1.2.1. Memorylessness¶

Let $$X$$ be a random variable supported on the nonnegative integers $$\ZZ_+$$.

We say that $$X$$ is geometrically distributed if, for some $$\theta$$ satisfying $$0 \leq \theta \leq 1$$,

(1.1)$\PP\{X = k\} = (1-\theta)^k \theta \qquad (k = 0, 1, \ldots)$

An example can be constructed from the discussion of the roulette wheel above.

Suppose that,

• the outcome of each spin is either red or black,

• spins are labeled by $$0, 1, 2, \ldots$$,

• on each spin, black occurs with probability $$\theta$$ and

• outcomes across spins are independent.

Then (1.1) is the probability that the first occurrence of black is at spin $$k$$.

(The outcome “black” fails $$k$$ times and then succeeds.)

Consistent with our discussion in the introduction, the geometric distribution is memoryless.

In particular, given any nonnegative integer $$m$$, we have

(1.2)$\PP \{X = m + 1 \,|\, X > m \} = \theta$

In other words, regardless of how long we have seen only red outcomes, the probability of black on the next spin is the same as the unconditional probability of getting black on the very first spin.

To establish (1.2), we use basic properties of the geometric distribution to obtain.

$\frac{ \PP \{X = m + 1 \text{ and } X > m \} } {\PP \{X \geq m\}} = \frac{ \PP \{X = m + 1 \} } {\PP \{X > m\}} = \frac{ (1-\theta)^{m+1} \theta } {(1-\theta)^{m+1} } = \theta$

## 1.3. The Exponential Distribution¶

Later, when we construct continuous time Markov chains, we will need to specify the distribution of the holding times, which are the time intervals between jumps.

As discussed above (and again below), the holding time distribution must be memoryless, so that the chain satisfies the Markov property.

While the geometric distribution is memoryless, its discrete support makes it a poor fit for the continuous time case.

Hence we turn to the exponential distribution, which is supported on $$\RR_+$$.

A random variable $$Y$$ on $$\RR_+$$ is called exponential with rate $$\lambda$$, denoted by $$Y \sim \Exp(\lambda)$$, if

$\PP\{Y > y\} = e^{-\lambda y} \qquad (y \geq 0)$

### 1.3.1. From Geometric to Exponential¶

The exponential distribution can be regarded as the “limit” of the geometric distribution.

To illustrate, let us suppose that

• customers enter a shop at discrete times $$t_0, t_1, \ldots$$

• these times are evenly spaced, so that $$h = t_{i+1} - t_i$$ for some $$h > 0$$ and all $$i \in \ZZ_+$$

• at each $$t_i$$, either zero or one customers enter (no more because $$h$$ is small)

• entry at each $$t_i$$ occurs with probability $$\lambda h$$ and is independent over $$i$$.

The fact that the entry probability is proportional to $$h$$ is important in what follows.

You can imagine many customers passing by the shop, each entering independently.

If we halve the time interval, then we also halve the probability that a customer enters.

Let

• $$Y$$ be the time of the first arrival at the shop,

• $$t$$ be a given positive number and

• $$i(h)$$ be the largest integer such that $$t_{i(h)} \leq t$$.

Note that, as $$h \to 0$$, the grid becomes finer and $$t_{i(h)} = i(h) h \to t$$.

Writing $$i(h)$$ as $$i$$ and using the geometric distribution, the probability that the first arrival occurs after $$t_{i}$$ is $$(1-\lambda h)^{i}$$.

Hence

$\PP\{Y > t_{i} \} = (1-\lambda h)^i = \left( 1- \frac{\lambda i h}{i} \right)^i$

Using the fact that $$e^x = \lim_{i \to \infty}(1 + x/i)^i$$ for all $$x$$ and $$i h = t_i \to t$$, we obtain, for large $$i$$,

$\PP\{Y > t\} \approx e^{- \lambda t}$

In this sense, the exponential is the limit of the geometric distribution.

### 1.3.2. Memoryless Property of the Exponential Distribution¶

The exponential distribution is the only memoryless distribution supported on $$\RR_+$$, as the next theorem attests.

Theorem 1.1 (Characterization of the Exponential Distribution)

If $$X$$ is a random variable supported on $$\RR_+$$, then there exists a $$\lambda > 0$$ such that $$X \sim \Exp(\lambda)$$ if and only if, for all positive $$s, t$$,

(1.3)$\PP \{X > s + t \,|\, X > s \} = \PP \{X > t\}$

Proof. To see that (1.3) holds when $$X$$ is exponential with rate $$\lambda$$, fix $$s, t > 0$$ and observe that

$\frac{ \PP \{X > s + t \text{ and } X > s \} } {\PP \{X > s\}} = \frac{ \PP \{X > s + t \} } {\PP \{X > s\}} = \frac{e^{-\lambda s - \lambda t}}{e^{-\lambda s}} = e^{-\lambda t}$

To see that the converse holds, let $$X$$ be a random variable supported on $$\RR_+$$ such that (1.3) holds.

The “exceedance” function $$f(s) := \PP\{X > s\}$$ then has three properties:

1. $$f$$ is decreasing on $$\RR_+$$,

2. $$0 < f(t) < 1$$ for all $$t > 0$$,

3. $$f(s + t) = f(s) f(t)$$ for all $$s, t > 0$$.

The first property is common to all exceedance functions, the second is due to the fact that $$X$$ is supported on all of $$\RR_+$$, and the third is (1.3).

From these three properties we will show that

(1.4)$f(t) = f(1)^t \;\; \forall \, t \geq 0$

This is sufficient to prove the claim because then $$\lambda := - \ln f(1)$$ is a positive real number (by property 2) and, moreover,

$f(t) = \exp( \ln ( f(1) ) t) = \exp( - \lambda t)$

To see that (1.4) holds, fix positive integers $$m,n$$.

We can use property 3 to obtain both

$f(m/n) = f(1/n)^m \quad \text{and} \quad f(1) = f(1/n)^n$

It follows that $$f(m/n)^n = f(1/n)^{m n} = f(1)^m$$ and, raising to the power of $$1/n$$, we get (1.4) when $$t=m/n$$.

The discussion so far confirms that (1.4) holds when $$t$$ is rational.

So now take any $$t \geq 0$$ and rational sequences $$(a_n)$$ and $$(b_n)$$ converging to $$t$$ with $$a_n \leq t \leq b_n$$ for all $$n$$.

By property 1 we have $$f(b_n) \leq f(t) \leq f(a_n)$$ for all $$n$$, so

$f(1)^{b_n} \leq f(t) \leq f(1)^{a_n} \quad \forall \, n \in \NN$

Taking the limit in $$n$$ completes the proof.

### 1.3.3. Failure of Memorylessness¶

We know from the proceeding section that any distribution on $$\RR_+$$ other than the exponential distribution fails to be memoryless.

Here’s an example that helps to clarify (although the support of the distribution is a proper subset of $$\RR_+$$).

A random variable $$Y$$ has the Pareto distribution with positive parameters $$t_0, \alpha$$ if

$\begin{split} f(t) := \PP\{Y > t\} = \begin{cases} 1 & \text{ if } t \leq t_0 \\ (t_0 / t)^\alpha & \text{ if } t > t_0 \end{cases} \end{split}$

As a result, with $$s > t_0$$,

$\PP \{Y > s + t \,|\, Y > s \} = \frac{ \PP \{Y > s + t \} } {\PP \{Y > s\}} = \left( \frac{t}{t + s} \right)^\alpha$

Since this probability falls with $$s$$, the distribution is not memoryless.

If we have waited many hours for an event (i.e., $$s$$ is large), then the probability of waiting another hour is relatively small.

## 1.4. Sums of Exponentials¶

A random variable $$W$$ on $$\RR_+$$ is said to have the Erlang distribution if its density has the form

$f(t) = \frac{\lambda^n t^{n-1}}{(n-1)!} e^{-\lambda t} \qquad (t \geq 0)$

for some $$n \in \NN$$ and $$\lambda > 0$$.

The parameters $$n$$ and $$\lambda$$ are called the shape and rate parameters respectively.

The next figure shows the shape for two parameterizations.

t_grid = np.linspace(0, 50, 100)

class Erlang:

def __init__(self, λ=0.5, n=10):
self.λ, self.n = λ, n

def __call__(self, t):
n, λ = self.n, self.λ
return (λ**n * t**(n-1) * np.exp(-λ * t)) / factorial(n-1)

e1 = Erlang(n=10, λ=0.5)
e2 = Erlang(n=10, λ=0.75)

fig, ax = plt.subplots()
for e in e1, e2:
ax.plot(t_grid, e(t_grid), label=f'$n={e.n}, \lambda={e.λ}$')

ax.legend()
plt.show()

The CDF of the Erlang distribution is

(1.5)$F(t) = \PP\{W \leq t\} = 1 - \sum_{k=0}^{n-1} \frac{(\lambda t)^k}{k!} e^{-\lambda t}$

The Erlang distribution is of interest to us because of the following fact.

Lemma 1.1 (Distribution of Sum of Exponentials)

If, for some $$\lambda > 0$$, the sequence $$(W_i)$$ is IID and exponentially distributed with rate $$\lambda$$, then $$J_n := \sum_{i=1}^n W_i$$ has the Erlang distribution with shape $$n$$ and rate $$\lambda$$.

This connects to Poisson process theory, as we shall soon see.

## 1.5. Exercises¶

Exercise 1.1

Due to its memoryless property, we can “stop” and “restart” an exponential draw without changing its distribution.

To illustrate this, we can think of fixing $$\lambda > 0$$, drawing from $$\Exp(\lambda)$$, and stopping and restarting whenever a threshold $$s$$ is crossed.

In particular, consider the random variable $$X$$ defined as follows:

• Draw $$Y$$ from $$\Exp(\lambda)$$.

• If $$Y \leq s$$, set $$X = Y$$.

• If not, draw $$Z$$ independently from $$\Exp(\lambda)$$ and set $$X = s + Z$$.

Show that $$X \sim \Exp(\lambda)$$.

Exercise 1.2

Fix $$\lambda = 0.5$$ and $$s=1.0$$.

Simulate 1,000 draws of $$X$$ using the algorithm above.

Plot the fraction of the sample exceeding $$t$$ for each $$t \geq 0$$ (on a grid) and compare to $$t \mapsto e^{-\lambda t}$$.

Is the fit good? How about if the number of draws is increased?

Are the results in line with those of the previous exercise?

## 1.6. Solutions¶

Note

code is currently not supported in sphinx-exercise so code-cell solutions are immediately after this solution block.

Solution to Exercise 1.1

Let $$X$$ be constructed as in the statement of the exercise and fix $$t > 0$$.

Notice that $$X > s + t$$ if and only if $$Y > s$$ and $$Z > t$$.

As a result of this fact and independence,

$\PP\{X > s + t\} = \PP\{Y > s \} \PP\{Z > t\} = e^{-\lambda(s + t)}$

At the same time, $$X > s-t$$ if and only if $$Y > s-t$$, so

$\PP\{X > s - t\} = \PP\{Y > s - t \} = e^{-\lambda(s - t)}$

Either way, we have $$X \sim \Exp(\lambda)$$, as was to be shown.

Solution to Exercise 1.2

Here’s one solution, starting with 1,000 draws.

λ = 0.5
np.random.seed(1234)
t_grid = np.linspace(0, 10, 200)

@njit
def draw_X(s=1.0, n=1_000):
draws = np.empty(n)
for i in range(n):
Y = np.random.exponential(scale=1/λ)
if Y <= s:
X = Y
else:
Z = np.random.exponential(scale=1/λ)
X = s + Z
draws[i] = X
return draws

fig, ax = plt.subplots()
draws = draw_X()
empirical_exceedance = [np.mean(draws > t) for t in t_grid]
ax.plot(t_grid, np.exp(- λ * t_grid), label='exponential exceedance')
ax.plot(t_grid, empirical_exceedance, label='empirical exceedance')
ax.legend()

plt.show()

Solution to Exercise 1.2

Solution Continued:

The fit is already very close, which matches with the theory in Exercise 1.

The two lines become indistinguishable as $$n$$ is increased further.

fig, ax = plt.subplots()
draws = draw_X(n=10_000)
empirical_exceedance = [np.mean(draws > t) for t in t_grid]
ax.plot(t_grid, np.exp(- λ * t_grid), label='exponential exceedance')
ax.plot(t_grid, empirical_exceedance, label='empirical exceedance')
ax.legend()

plt.show()


text:
# Claw-free graph - linear kernel

I'm having a hard time solving the problem below:

In Claw-free problem, we are given a graph $$G$$ and $$k$$, and the objective is to decide whether there exists a subset $$S \subseteq V (G)$$ of size at most $$k$$ such that $$G \setminus S$$ does not contain any $$3$$-star (known also as a claw) as a subgraph. Design an $$O(k)$$-vertex kernel for Claw-free problem. There's a hint which says we can use a $$4$$-approximation polynomial-time algorithm for $$4$$-Hitting Set as a black box.

Thanks!!!

• Hi Tami. Welcome to CS.stackexchange. The question is interesting. However, you should cite the original source of this problem (see help). – Inuyasha Yagami Jun 14 at 6:51
• And, it is unlikely that you will receive help unless you mention what you have tried so far. – Inuyasha Yagami Jun 14 at 6:52
• Well its a question from parameterized algorithms book.. we learned some techniques but can think about something specificaly. – Tami H Jun 14 at 11:11
• Hi Tami. I have a few ideas; however, I couldn't solve the problem. I also want to know the solution. So, I will perhaps write a different question with some ideas that I have tried. I couldn't find this problem in the "Parameterized Algorithms" book of Cygan et al. Can you please share the exact reference of this problem? – Inuyasha Yagami Jun 14 at 14:16


text:
D. Almost All
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree with $n$ nodes. You have to write non-negative integers on its edges so that the following condition would be satisfied:

For every two nodes $i$, $j$, look at the path between them and count the sum of numbers on the edges of this path. Write all obtained sums on the blackboard. Then every integer from $1$ to $\lfloor \frac{2n^2}{9} \rfloor$ has to be written on the blackboard at least once.

It is guaranteed that such an arrangement exists.

Input

The first line contains a single integer $n$ ($1 \le n \le 1000$) — the number of nodes.

Each of the next $n-1$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n$, $u \neq v$), meaning that there is an edge between nodes $u$ and $v$. It is guaranteed that these edges form a tree.

Output

Output $n-1$ lines, each of form $u$ $v$ $x$ ($0 \le x \le 10^6$), which will mean that you wrote number $x$ on the edge between $u$, $v$.

Set of edges $(u, v)$ has to coincide with the set of edges of the input graph, but you can output edges in any order. You can also output ends of edges in an order different from the order in input.

Examples
Input
3
2 3
2 1

Output
3 2 1
1 2 2

Input
4
2 4
2 3
2 1

Output
4 2 1
3 2 2
1 2 3

Input
5
1 2
1 3
1 4
2 5

Output
2 1 1
5 2 1
3 1 3
4 1 6

Note

In the first example, distance between nodes $1$ and $2$ is equal to $2$, between nodes $2$ and $3$ to $1$, between $1$ and $3$ to $3$.

In the third example, numbers from $1$ to $9$ (inclusive) will be written on the blackboard, while we need just from $1$ to $5$ to pass the test.


text:
The General Solution for a Constant Potential

We have found the general solution of the Schrödinger Equation in a region in which the potential is constant. Assume the potential is equal to and the total energy is equal to . Assume further that we are solving the time independent equation.

For , the general solution is

with positive and real. We could also use the linear combination of the above two solutions.

We should use one set of solutions or the other in a region, not both. There are only two linearly independent solutions.

The solutions are also technically correct for but becomes imaginary. For simplicity, lets write the solutions in terms of , which again is real and positive. The general solution is

These are not waves at all, but real exponentials. Note that these are solutions for regions where the particle is not allowed classically, due to energy conservation; the total energy is less than the potential energy. Nevertheless, we will need these solutions in Quantum Mechanics.

Jim Branson 2013-04-22


text:
SERVING THE QUANTITATIVE FINANCE COMMUNITY

Posts: 23951
Joined: September 20th, 2002, 8:30 pm

### Re: If you are bored with Deep Networks

The fundamental working hypothesis of AI is that intelligent behavior can be precisely described as symbol manipulation and can be modeled with the symbol processing capabilities of the computer.

??
The 1980s called and they want their hypothesis back.

ISayMoo
Topic Author
Posts: 2294
Joined: September 30th, 2015, 8:30 pm

### Re: If you are bored with Deep Networks

It's still true. Only we need to build this computer first.

Cuchulainn
Posts: 62106
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: If you are bored with Deep Networks

Does Tensorflow support multi-processor CPUs and can it be customised?

Cuchulainn
Posts: 62106
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: If you are bored with Deep Networks

Does Tensorflow support multi-processor CPUs and can it be customised? e.g. if you don't have GPUs or Cloud?
What's the speedup for this application? What's the maximum number of cores before performance degrades? I suppose it uses a fine-grained thread model with locking and pre-emption?

tagoma
Posts: 18354
Joined: February 21st, 2010, 12:58 pm

### Re: If you are bored with Deep Networks

with tf.device("/cpu:4"):
# ...

with tf.device("/cpu:7"):
# ...

with tf.device("/cpu:0"):
# ...

config = tf.ConfigProto(device_count={"CPU": 8},
sess = tf.Session(config=config)

Cuchulainn
Posts: 62106
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: If you are bored with Deep Networks

import time
def wait_on_b():
time.sleep(5)
print(b.result())  # b will never complete because it is waiting on a.
return 5

def wait_on_a():
time.sleep(5)
print(a.result())  # a will never complete because it is waiting on b.
return 6

a = executor.submit(wait_on_b)
b = executor.submit(wait_on_a)
I don't use Python(yet) but the issues are language-independent. Threads scale badly and anecdotal evidence shows that speedup in TensorFlow is bad with > 32 processors. Too fine-grained.

Python supports asynchronous futures which offer an alternative (C++11 has futures). The Scheduler determines what is pinned to what, not the application developer (sub-optimal).

https://docs.python.org/3/library/concu ... tures.html

mkoerner
Posts: 4
Joined: April 8th, 2009, 12:17 pm

### Re: If you are bored with Deep Networks

Does Tensorflow support multi-processor CPUs and can it be customised? e.g. if you don't have GPUs or Cloud?
What's the speedup for this application? What's the maximum number of cores before performance degrades? I suppose it uses a fine-grained thread model with locking and pre-emption?
As far as I know it supports multi-core CPUs on a number of levels, on a low level by dispatching calls to the MKL, and on a high level by running multiple sessions in parallel (FAQ, Does the runtime parallelize parts of graph execution?). Similar in pytorch where on a high-level the input data can be distributed along a dimension using DataParallelThis post on "Python Global Interpreter Lock (GIL) + numerical data processing" could also be informative if you are interested in Python.

Cuchulainn
Posts: 62106
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: If you are bored with Deep Networks

History of the tools

Logistic regression — 1958
Hidden Markov Model — 1960
Support Vector Machine — 1963
k-nearest neighbors — 1967
Artificial Neural Networks — 1975
Expectation Maximization — 1977
Decision tree — 1986
Q-learning — 1989
Random forest — 1995

Cuchulainn
Posts: 62106
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: If you are bored with Deep Networks

I find trying to grasp all these articles a bit painful. Lots of theory/theorems etc. but where is the example? e.g. that you can check against.

Posts: 23951
Joined: September 20th, 2002, 8:30 pm

### Re: If you are bored with Deep Networks

I find trying to grasp all these articles a bit painful. Lots of theory/theorems etc. but where is the example? e.g. that you can check against.

This does not sound right to me. My (limited) experience of math has been the opposite. Examples are mostly for applied math.

I wonder what percentage of academic math papers have examples?

Cuchulainn
Posts: 62106
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: If you are bored with Deep Networks

Maybe this example helps.(sections 3 and 5)
https://en.wikipedia.org/wiki/Metric_space

'Concrete' can be at many 'levels' e.,g. objects and types.
Just think about metrics for NNs, input representation and the mappings (hopefurrry bijective) between metric spaces etc.

Cuchulainn
Posts: 62106
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: If you are bored with Deep Networks

Some open research issues(??)
https://pdfs.semanticscholar.org/a2cf/2 ... 9e43dc.pdf

and some guidelines ..

https://www.ucl.ac.uk/~ucfamus/papers/i ... ions17.pdf

It would be useful for the august panel to give their feedback.

ISayMoo
Topic Author
Posts: 2294
Joined: September 30th, 2015, 8:30 pm

### Re: If you are bored with Deep Networks

The 1st article is very old (from 2007). A lot of the stuff in it is out of date or applies to things people are no longer really interested in.

The 2nd article (guidelines) is kind of "Captain Obvious speaking" paper. The author's right about everything (or maybe almost everything, but I didn't have the time to go nitpicking), but it's rather well-known stuff.

Cuchulainn
Posts: 62106
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: If you are bored with Deep Networks

The 1st article is very old (from 2007). A lot of the stuff in it is out of date or applies to things people are no longer really interested in.

The 2nd article (guidelines) is kind of "Captain Obvious speaking" paper. The author's right about everything (or maybe almost everything, but I didn't have the time to go nitpicking), but it's rather well-known stuff.
Fair enough.So things have progressed in leaps and bounds in the period 2007-2017?
2007 is not very old. BP is at least 50 years old.

Cuchulainn
Posts: 62106
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: If you are bored with Deep Networks

The recent spate of articles are great on description and narrative (the what) but fall short on explanation (the how), as Wittgenstein might say.

Reverse engineering is well-nigh impossible. It's all black box anno 2007 or has that been resolved, ISayMoo?

Does university education not teach how to write unambiguous algorithms?


text:
# Asger Tornquist: An invariant set-theoretic approach to Mathias’ theorem

Place: Fields Institute (Room 210)

Date: May 20, 2016 (13:30-15:00)

Speaker: Asger Tornquist

Title: An invariant set-theoretic approach to Mathias’ theorem

Abstract: Mathias proved in 1969 that there are no infinite analytic
maximal almost disjoint families of subsets of $\omega$. His proof is
essentially Ramsey theoretical. A few years ago I found a “classical” proof
of this theorem which uses a tree/derivative argument. But in this talk, I
will give yet another proof, this time one that is closer in spirit to
Mathias’ original proof, but which avoids the Ramsey theoretical machinery
by instead using a bit of garden-variety invariant descriptive set theory.


text:
## How to find the distances between two adjacent maxima in a solution from NDSolve

I try to find a general approach to plot the time evolution of horizontal distances from maximum to maximum in a solution of PDE. The solution u[x,t] normally have multiple maximum and minimum in space x, which move in space x and evolve in time t.

Here is a simple example, in which the maxima and minima are periodic. But in my real problem they are not periodic and the distances between different pairs of adjacent max are different at a given t, also the distances between two adjacent max can change with t.

sol = NDSolve[{D[u[x, t], t] + u[x, t] D[u[x, t], x] + D[u[x, t], x, x] +  0.4*D[u[x, t], {x, 3}] + D[u[x, t], {x, 4}] == 0, u[-4 \[Pi], t] == u[4 \[Pi], t], u[x, 0] == 0.1*Sin[x]}, u, {t, 0, 20}, {x, -4 \[Pi], 4 \[Pi]}]  Plot3D[Evaluate[u[x, t] /. First[sol]], {t, 0, 10}, {x, -4 Pi, 4 Pi}, PlotRange -> All, PlotPoints -> 100]

I have tried to use Table[FindMaximum[Evaluate[u[x, t] /. First[sol]], {x, x0}][[2, 1, 2]], {t,0,tend,0.01}] with an initial position x0 to find a local maximum. But I don’t know how to find two adjacent maxima simultaneously in order to plot the time evolution of their distance.

## Calculating the maxima of a function subject to a constraint

The first figure below shows the plots of a function $$f(x)$$ plotted for different values of a parameter $$\lambda$$, i.e., $$f(x)=f(x,\lambda=\lambda_i);i=1,2,3,..;\lambda$$ is maximum for the topmost curve and decreases downwards. The second figure shows the values of $$\lambda$$ that corresponds to the extrema.

Each curve has one maxima and one minima. The dotted curve corresponds to the case that has no maxima or minima, i.e., the value of $$\lambda$$ corresponding to the dotted curve is the threshold for existence of any extrema.

Note that figure-1 is obtained from particle dynamics where we have an expression for $$f(x)$$ and we can obtain figure-2 by calculating the extreme values. However, in hydrodynamics we can only obtain figure-2 which matches exactly with that of particle dynamics. In this sense, figure-2 is the same for particle dynamics as well as hydrodynamics.

The following are my goals:

• To find the threshold value of $$\lambda$$ (corresponding to the black dotted curve): This I had already calculated by finding the minima of the $$\lambda-x$$ curve.
• To find the value of $$\lambda$$ for which $$f(x)=1$$ (corresponding to the black solid curve): Since all the points on the $$\lambda-x$$ curve corresponds to extremum, I do not have any idea about how to use the constraint $$f(x)=1$$ as the expression for $$f(x)$$ is not available.

• In figure-1, all the curves saturates at $$f(x)=1$$ at large values of $$x$$. So the constraint $$f(x)=1$$ is satisfied for the black(solid) curve as seen in the figure at $$x=2.91$$ and also for all the curves at large $$x$$. So I think that the asymptotic behaviour of $$f(x)$$ might be related to the values of $$\lambda$$.

• In figure-2, initially $$\lambda$$ decreases steeply with $$x$$ and after the minima, $$\lambda$$ varies as $$\lambda=\sqrt x$$.

Any hint about the approach to solve the problem would be sufficient.

## Find all local maxima in a one-dimensional array

I implemented the following class (it works) and I just want to hear your opinions about best practices and what can be improved. The idea was to do it using mostly arrays.

The class just finds the peak elements in an array with respect to their neighbors. The first element and the last element are ignored.

Example: {3, 15, 5, 20, 10} Answer: {15, 20}

package findpeak;  import java.util.ArrayList; import java.util.List;   public class ArrayPeak {     private final int[] ARRAY;     private final int LEN;     private static final int IGNORE_FIRST_POSITION = 0;     private final int IGNORE_LAST_POSITION;      public ArrayPeak(int[] array)     {         this.ARRAY = array;         this.LEN = this.ARRAY.length;         this.IGNORE_LAST_POSITION = this.LEN - 1;     }      public List<Integer> findPeaks()     {         List<Integer> peaks = new ArrayList<>();         for (int position = 0; position < LEN; position++)         {             int output = 0;             if (position != IGNORE_FIRST_POSITION && position != IGNORE_LAST_POSITION)             {                 int[] trippleArray =                 {                     ARRAY[position - 1], ARRAY[position], ARRAY[position + 1]                 };                 output = checkPeak(trippleArray);             }             peaks.add(output);         }          return filterZeros(peaks);     }      private static int checkPeak(int[] inputArray)     {         int peak = 0;         if (inputArray[1] > inputArray[0] && inputArray[1] > inputArray[2])         {             peak = inputArray[1];         }         return peak;     }      private static List<Integer> filterZeros(List<Integer> list)     {         List<Integer> filteredList = new ArrayList<>();         for (int i = 0; i < list.size(); i++)         {             if (list.get(i) != 0)             {                 filteredList.add(list.get(i));             }         }         return filteredList;     } }

## Maxima of Brownian motion

It is well-known that Brownian motion attains infinitely many maxima in each time interval $$[0,T]$$ a.s..

From a physics perspective it seems reasonable that when the disorder of the path of a particle decreases and the motion becomes more deterministic, then the number of maxima should decrease.

But I could not find anything on that. Now, there were two natural things to look at:

Is there a way to quantify that a Brownian motion with large variance (large disorder) has more maxima than one with little disorder?

Or is there a way to say that a diffusion process

$$dX_t = \mu (X_t) \ dt + \alpha dB_t$$

has “less” maxima when $$\alpha$$ is small compared to $$\alpha$$ large?

I guess it is hard to make this question more precise, since this is not a question of cardinality of maxima but more about finding a suitably chosen measure that could capture such an effect.

## About maxima of injective holomorphic maps on $\mathbb{C}^n$

I am hoping the following is true. Mention of related ideas/topics are appreciated.

Suppose $$F:\mathbb{C}^n \to \mathbb{C}^n$$ is a injective holomorphic mapping such that $$F(0)=0$$ and $$dF(0) = I_n$$ where $$I_n$$ is the $$n \times n$$ identity matrix. Let $$\partial B$$ denote the boundary of the unit ball centered at the origin in $$\mathbb{C}^n$$. Let $$M = \sup_{x \in \partial B} ||F(x)||$$ where $$|| \cdot ||$$ is the usual Euclidean norm. Then $$\partial B \cap \{x: M = ||F(x)|| \}$$ is equal to one of three things: i) $$\{p\}$$ for some point $$p$$, ii) $$\{\alpha p : |\alpha|=1 \}$$ for some point $$p$$, iii) $$\partial B$$

Let $$F\subset \mathbb{R}^n$$ be a finite set and $$\sigma$$ be uniformly distributed over $$\{-1,1\}^n$$. The usual Rademacher average of $$F$$ (modulo normalizing factors) is $$R_n(F)=\mathbb{E}_\sigma \max_{f\in F}\sum_{i=1}^n \sigma_if_i.$$ Now let us define two operations on $$F$$: $$\mathrm{conv}(F)$$ and $$[F]_\vee$$. The former is just the convex hull of the vector-set $$F$$ in $$\mathbb{R}^n$$. The latter is defined by $$[F]_\vee=\{ f\vee g :f,g \in F\},$$ where $$(f\vee g)_i=\max\{f_i,g_i\}$$ is the coordinate-wise maximum.

Question: is it true that $$R_n( [\mathrm{conv}(F)]_\vee) \le R_n( [F]_\vee)$$ ?

## On sums of minima and maxima

Let $$h_1,\ldots,h_n$$ be positive integers, and define $$m(h_1,\ldots,h_n)=\sum_{r_1=0}^{h_1-1}\ldots\sum_{r_n=0}^{h_n-1}\min\left\{\frac{r_1}{h_1},\ldots,\frac{r_n}{h_n}\right\}$$ and $$M(h_1,\ldots,h_n)=\sum_{r_1=0}^{h_1-1}\ldots\sum_{r_n=0}^{h_n-1}\max\left\{\frac{r_1}{h_1},\ldots,\frac{r_n}{h_n}\right\}.$$ Motivated by Dedekind sums, I introduced $$m(h_1,\ldots,h_n)$$ and $$M(h_1,\ldots,h_n)$$ in my paper in Discrete Math. 257(2002), 143-159, and determined their exact values for $$n\le 3$$ in that paper. For example, I showed that if $$h,k,l$$ are positive integers then \begin{align} m(h,k,l)=&\frac{hkl}4-\frac{hk+hl+kl}6+\frac{h+k+l-1}8 \&+\frac{h+k-2hk}{24l}+\frac{h+l-2hl}{24k}+\frac{k+l-2kl}{24h} \&+\frac{(h-1)(k,l)^2}{24kl}+\frac{(k-1)(h,l)^2}{24hl}+\frac{(l-1)(h,k)^2}{24hk}, \end{align} where $$(a,b)$$ denotes the greatest common divisor of integers $$a$$ and $$b$$.

QUESTION. Are $$m(h_1,\ldots,h_n)$$ and $$M(h_1,\ldots,h_n)$$ rational functions in $$h_1,\ldots,h_n$$ whenever $$h_1,\ldots,h_n$$ are pairwise coprime?

I conjectured that this question has a positive answer in the mentioned 2002 paper of mine.

## Local maxima 3D array python

Hi I’m trying to find local maxima in a 3D numpy array, but I can’t seem to find a easy way to do that using numpy, scipy, or anything else.

For now I implemented it using scipy.signal.argrelexrema. But it’s very long to process large arrays, and only works on separated axis.

import numpy as np from scipy.signal import argrelextrema   def local_maxima_3D(data, order=1):     """Detects local maxima in a 3D array      Parameters     ---------     data : 3d ndarray     order : int         How many points on each side to use for the comparison      Returns     -------     coordinates : ndarray         coordinates of the local maxima     values : ndarray         values of the local maxima     """     # Coordinates of local maxima along each axis     peaks0 = np.array(argrelextrema(data, np.greater, axis=0, order=order))     peaks1 = np.array(argrelextrema(data, np.greater, axis=1, order=order))     peaks2 = np.array(argrelextrema(data, np.greater, axis=2, order=order))      # Stack all coordinates     stacked = np.vstack((peaks0.transpose(), peaks1.transpose(),                          peaks2.transpose()))      # We keep coordinates that appear three times (once for each axis)     elements, counts = np.unique(stacked, axis=0, return_counts=True)     coords = elements[np.where(counts == 3)[0]]      # Compute values at filtered coordinates     values = data[coords[:, 0], coords[:, 1], coords[:, 2]]      return coords, values

I know this solution is far from optimal and only works with order=1. Is there any better way to find local maxima in a 3D array in python ?

## Finding maxima of a function $f(x) = \sqrt{x} – 2x^2$ without calculus

My question is how to prove that $$f(x) = \sqrt x – 2x^2$$ has its maximum at point $$x_0 = \frac{1}{4}$$

It is easy to do that by finding its derivative and setting it to be zero (this is how I got $$x_0 = \frac{1}{4}$$). But the task is to do that without using any calculus tools and I`m stuck at it.

My idea was to introduce $$t = \sqrt x$$ to get $$f(t) = t – 2t^4$$ and then find its maximum because I know how to do that with parabola which can be transformed to $$a(x-x_0)^2 + y_0$$. So I was trying to turn $$f(t) = t – 2t^4$$ into $$f(t) = a(x-x_0)^4 + y_0$$ but it seems impossible.

My second thought was to use the definition of rising function on an interval so I supposed we have $$a, b \in \left(0; \frac{1}{4}\right) \text{and } a < b$$. Then I prove that $$\sqrt a – 2a^2 < \sqrt b – 2b^2$$ $$2(b – a)(a + b) < \sqrt b – \sqrt a$$ $$2(\sqrt a + \sqrt b)(a + b) < 1$$ which is true since $$0 < a < b < \frac{1}{4}$$

Exactly the same way I prove that for every $$a, b \in \left(\frac{1}{4}; +\infty\right) \text{and } a < b$$ $$\sqrt a – 2a^2 > \sqrt b – 2b^2$$

So we have that $$f(x)$$ is rising on $$\left(0; \frac{1}{4}\right)$$ and declining on $$\left(\frac{1}{4}; +\infty\right)$$, consequently at $$\frac{1}{4}$$ we have a maximum of $$f$$

But I guess it is not fair to use derivatives to find the maximum and then simply prove that this value is correct. Is there an even better solution? What are your thoughts about my proof?