text:
Government Center, Boston

Government Center is an area in downtown Boston, centered on City Hall Plaza. Formerly the site of Scollay Square, it is now the location of Boston City Hall, courthouses, state and federal office buildings, and a major MBTA subway station, also called Government Center. Its development was controversial, as the project displaced thousands of residents and razed several hundred homes and businesses.

Controversial in design since before it was completed, the use of Brutalist architecture for its main buildings, as well as the open brick-and-concrete plaza at the center of the development, have been alternately praised for its innovative design, and scorned for its lack of character and uninviting appearance. After decades of calls for a redesign to make it more friendly and usable, a major rebuild of City Hall Plaza, the main public space of Government Center, was begun in 2020 and is to include additional seating areas, play spaces for children, and space for public art.

Post-colonial development and commerce
Scollay Square was named for William Scollay, a prominent local developer and militia officer who bought a landmark four-story merchant building at the intersection of Cambridge and Court Streets in 1795. Local citizens began to refer to the intersection as Scollay's Square, and, in 1838, the city officially memorialized the intersection as Scollay Square.

Early on, the area was a busy center of commerce, including the city's first daguerreotypist (photographer), Josiah Johnson Hawes (1808–1901), and Dr. William Thomas Green Morton, the first dentist to use ether as an anaesthetic.

Local cultural landmarks took form, attracting visits from such intellectual contemporaries as Charles Dickens.

Abolitionism
Scollay Square was also a flashpoint for the early abolition movement. Author William Lloyd Garrison was twice attacked by an angry mob for printing his anti-slavery newspaper The Liberator, which began publication in 1831. Sarah Parker Remond's first act of civil disobedience occurred in 1853 at the Old Howard when she was refused the seat she had purchased but was instead seated in the 'black' section. Many of the buildings in the area in and around Scollay Square had hidden spaces where escaped slaves were hidden, as part of the Underground Railroad.

The Old Howard
Among the most famous (and infamous) of Scollay Square landmarks was the Old Howard Theatre, a grand theater which began life as the headquarters of a Millerite Adventist Christian sect which believed the world would end in October 1844. After the world failed to end on schedule, the building was sold in 1844 and reopened as a vaudeville and Shakespearean venue. Later, in the 1900s and 1910s, it would showcase the popular minstrel shows.

By around the 1940s the Scollay Square area began to lose its vibrant commercial activity, and the Howard gradually changed its image and began to cater to sailors on leave and college students by including burlesque shows, as did other nearby venues such as the Casino Theater and Crawford House. "Always Something Doing" became the Old Howard's advertising slogan. The venue also showcased boxing matches with such old-time greats as local Rocky Marciano and John L. Sullivan, and continued to feature slapstick vaudeville acts, from likes of The Marx Brothers and Abbott and Costello.

But it was the success and prominence of the burlesque shows that brought the Old Howard down. In 1953, vice squad agents sneaked a home movie camera into the Old Howard, and caught Mary Goodneighbor on film doing her striptease for the audience. The film led to the closure of the theater, and it remained closed until it caught fire mysteriously in 1961.

The square was also the home of Austin and Stone's Dime Museum.

Destruction and redevelopment
As early as the 1950s, city officials had been mulling plans to completely tear down and redevelop the Scollay Square area, in order to remove lower-income residents and troubled businesses from the aging and seedy district. Attempts to reopen the sullied Old Howard by its old performers had been one of the last efforts against redevelopment; but with the theater gutted by fire, a city wrecking ball began the project of demolishing over 1000 buildings in the area; 20,000 residents were displaced.

With $40 million in federal funds, the city built an entirely new development on top of old Scollay Square, renaming the area Government Center, and peppering it with city, state, and federal government buildings.

A 1958 report by the Boston Planning Board, entitled Government Center Project, set out the case for construction of a center:

"The future of Boston depends in large degree on how effectively and efficiently it continues to perform its role as the central city of an important metropolitan area and as the regional center for New England. ... One of the basic functions of such a regional center is the provision of governmental services at all levels. ... At the present time the accommodations in Boston for all levels of government are inadequate and inefficient."

Boston City Hall

The dominant feature of Government Center is the enormous, imposing, and brutalist Boston City Hall, designed by Kallmann McKinnell & Wood and built in the 1960s as part of Boston's first large urban renewal scheme. While considered by some to have architectural merit, the building is not universally admired, and is sharply unpopular among locals. Furthermore, it is resented for having replaced the Victorian architecture of Boston's Scollay Square, a lively commercial district that lapsed into squalor in the twentieth century.

John Fitzgerald Kennedy Federal Building
John Fitzgerald Kennedy Federal Building is a United States government office building. It is located across City Hall Plaza from Boston City Hall. An example of 1960s modern architecture, it consists of two 26 floor towers that sit on-axis to each other and a low rise building of four floors that connects to the two towers via an enclosed glass corridor. The two towers stand at a height of 118 m.

City Hall Plaza

City Hall Plaza is not a well-loved space, either. As Bill Wasik wrote in 2006, "It is as if the space were calibrated to render futile any gathering, large or small, attempted anywhere on its arid expanse. All the nearby buildings seem to be facing away, making the plaza's 11 acre of concrete and brick feel like the world's largest back alley. ... [It is] so devoid of benches, greenery, and other signposts of human hospitality that even on the loveliest fall weekend, when the Common and Esplanade and other public spaces teem with Bostonians at leisure, the plaza stands utterly empty save for the occasional skateboarder…" The plaza is often colloquially referred to as "the brick desert."

Government Service Center

Another very large Brutalist building at Government Center, less prominently located and thus less well known than City Hall, is the Government Service Center, designed by architect Paul Rudolph. The building is unfinished as the tall central tower in the original plan was never built. In the mid-1990s, the adjacent space was filled with the Edward W. Brooke Courthouse, which houses a division of the Boston Municipal Court. This irregularly shaped, sloping lot was the last parcel to be developed of the Government Center urban renewal plan; in the interim the space was used as surface parking. In a 2014 article, architectural historian Timothy M. Rohan praised the building for having "a wondrous interior courtyard like something from baroque Rome, a space that even in its incomplete and neglected state contrasts sharply with nearby City Hall and its alienating plaza."

Government Center Garage
This 2,300-space privately owned garage was built as part of the Government Center urban renewal project. In 2016, the Boston Redevelopment Authority gave final approval for the replacement of the garage with "Bulfinch Crossing," a 2.9 e6sqft mixed-use development   designed by Pelli Clarke Pelli Architects. Construction began in January 2017. The design of the office tower was revealed in June 2019.

Center Plaza

This 720,000 sqfoot office and retail structure, built by developer Norman B. Leventhal, is across Cambridge Street from City Hall Plaza. In 2014, the property was sold by the Blackstone Group to Shorenstein Properties. Shorenstein Properties has proposed a $25 million renovation designed "to add some new buzz" to the building. The renovation was approved by the Boston Redevelopment Authority in 2016.

Nearby public buildings
Several state and federal government buildings near Government Center were not built as part of the urban renewal project. These include the Massachusetts State House, the McCormack Building, the Saltonstall Building, the Suffolk County Courthouse, and the Thomas P. O'Neill Jr. Federal Building.

Sears' Crescent and Sears' Block
The Sears' Crescent and Sears' Block are a pair of 19th century buildings that border City Hall Plaza on the south.

The golden steaming kettle mounted on the corner of the Sears' Block, 63-65 Court Street, pre-dates the Government Center redevelopment. It was manufactured for the Oriental Tea Company in 1873, which held a contest to guess the volume of the kettle and staged a spectacle in which nine children and a tall man crawled out of the kettle. Its volume was measured by the city's official sealer of weights and measures at 227 gallons, 2 quarts, 1 pint, and 3 gills, (227+15/32 USgal) which for a time was painted on the side. The tea shop at 85-87 Court Street was demolished, but the owner, Nathan Sharaf, opened Steaming Kettle Coffee Shop in the new building and mounted the kettle. It became Croissant Du Jour in 1988, then Coffee Connection, then Starbucks in 1997.

Geography and transportation
Government Center is located between the North End, Downtown, and Beacon Hill neighborhoods.

Boundaries
Government Center does not have official boundaries. A 2011 Boston Redevelopment Authority map of Boston neighborhoods shows most of the Government Center area as part of the Downtown neighborhood, and the rest as part of the West End.

Other maps and documents show a variety of different boundaries for Government Center. The Boston Zoning Code has a map called "1H Government Center/Markets District." The map shows the Government Center portion of the district extending as far west as the Massachusetts State House and including all of the major structures listed in this article. The Boston Redevelopment Authority map of "Urban Renewal Areas" includes a somewhat smaller area that excludes the McCormack and Saltonstall Buildings.

By contrast, a search for "Government Center" on Google Maps yields a map showing an even smaller area that is bounded by Court, Cambridge, Sudbury, and Congress Streets. The AirBnB neighborhood map shows a somewhat larger area than the Google Map. An undated Boston Redevelopment Authority map entitled "Government Center Urban Renewal Area Illustrative Site Plan" showed similar boundaries.

Mass transit

Scollay Square station opened as part of the third phase of the Tremont Street Subway in September 1898, bringing subway service to the area with a stone headhouse in the center of the square. Court Street station opened on the East Boston Tunnel in December 1904; it was closed in 1914 and replaced by a lower level (Scollay Under) to the Scollay Square station in 1916. The station was rebuilt in 1963 as Government Center station with a low brick headhouse, and again from 2014 to 2016 with a large glass headhouse that dominates the south side of the plaza. It serves as the transfer point between the MBTA's Blue and Green Lines.

Surroundings
Government Center is adjacent to historic Faneuil Hall and popular Quincy Market and very near the Old State House. It is two blocks away from the Rose Fitzgerald Kennedy Greenway, which was created as part of the Big Dig. Major city streets in the vicinity include Tremont, Congress, Cambridge, State, New Chardon, and Washington Streets. Hints of another street, Cornhill, still exist along one edge of City Hall Plaza. Two of the neighborhood's few remaining old buildings, the Sears' Crescent and Sears' Block, face the plaza and follow the original curve of Cornhill. A veteran's home & services provider, still has an entrance with a Cornhill address. Plans for Government Center, including the Boston Redevelopment Authority's "Government center 2000 project", called for the construction of two footbridges over Congress Street to connect City Hall Plaza to the Faneuil Hall area. Neither bridge was built.

title: Government Center, Boston


text:
David Nalbandian

David Pablo Nalbandian (born 1 January 1982) is an Argentine former professional tennis player. He reached his highest ranking in singles of world No. 3 in March 2006, during a career that stretched from 2000 to 2013. Nalbandian was runner-up in the singles event at the 2002 Wimbledon Championships. During his career, he won 11 singles titles, including the Tennis Masters Cup in 2005 and two Masters 1000 tournaments. Nalbandian is the only Argentine man in history to reach the semifinals or better at all four majors and to reach the Wimbledon final. He was a member of the Argentinian Davis Cup team who reached the finals of the World Group in 2006, 2008 and 2011. Nalbandian played right-handed with a two-handed backhand, which was known for being a devastating shot. Since his retirement, Nalbandian has taken up the sport of rally racing and has competed in Rally Argentina.

Biography
Of Armenian and Italian descent, David Nalbandian was born in the small city of Unquillo in Córdoba Province, Argentina. He became a professional tennis player at the age of 18.

Junior career
As a junior, Nalbandian reached as high as No. 3 in the world in December 1998 (and No. 5 in doubles in 2000), soon after winning the US Open boys' singles final over fellow junior Roger Federer.

2000–2002
He turned professional in 2000. In 2001, he finished in the ATP top 50 for the first time. He finished 2002 as the No. 1 Argentine and South American for the first time in his career, winning two ATP titles and reaching the Wimbledon final, where he beat David Sánchez, Paul-Henri Mathieu, George Bastl, Wayne Arthurs, Nicolás Lapentti and Xavier Malisse before losing to Lleyton Hewitt.

2003–2004
Nalbandian did not reach another major final in 2003. At Wimbledon he lost to Tim Henman, following a stomach injury during his previous match against Karol Kucera. In 2004, Nalbandian achieved his best result at the French Open reaching the semifinals, losing to eventual champion Gastón Gaudio. Although he did not win any titles in 2004, he did finish runner-up at both the Rome Masters and the Madrid Masters,by Carlos Moyá and Marat Safin respectively. He broke into the top 5 for the first time in his career in August and finished 2004 ranked as the World No. 9 player.

2005
In 2005, Nalbandian advanced to the quarterfinals of the Australian Open, Wimbledon, and the U.S. Open. At Wimbledon, Nalbandian came from two sets down to defeat Andy Murray in the third round, in what was Murray's first Major tournament. , he remains the only player to ever defeat Murray from two sets down. He also won the Tennis Masters Cup, becoming only the second Argentine tennis player in history (after Guillermo Vilas in 1974) to win the year-end tournament. Having replaced Andy Roddick, he won two of his three group matches (to Federer, Ivan Ljubičić, and Guillermo Coria). In the semifinals, he defeated Russian Nikolay Davydenko, and in the final, he beat World No. 1 Roger Federer in a fifth-set tiebreak after coming from two sets down, with Federer succumbing to a right ankle injury after laboring out the first two sets in tiebreaks. Nalbandian became the first player to win the cup without previously attaining a Grand Slam or Masters Series title.

2006
In January 2006, Nalbandian beat Fabrice Santoro of France, 7–5, 6–0, 6–0, in the quarterfinals of the Australian Open, becoming, at the time, only the second active player (along with Roger Federer) to have reached the semifinals of each Grand Slam tournament. He lost in the semifinals to Marcos Baghdatis in a hard-fought five-set match, despite holding a two-set-to-love advantage and four games to two in the final set. In May, he won the Estoril Open Tournament in Portugal for the second time, being one of only three men to achieve this accomplishment (Carlos Costa, 1992 and 1994; and Thomas Muster, 1995 and 1996). One month later, Nalbandian reached his second French Open semifinal. It was the only time in his career that he reached two Grand Slam semifinals in one calendar year. He played Federer and started strongly, winning the first set 6–3 and going 3–0 up in the second set. At 5–2 down in the third set, Nalbandian decided to retire from the match due to stomach injury. At Wimbledon, Nalbandian was beaten in the third round, where he lost to Fernando Verdasco in straight sets. At the US Open, Nalbandian was beaten in the second round by Marat Safin.

Nalbandian then competed in the Davis Cup semifinal tie against Australia. David easily won against Mark Philippoussis, 6–4, 6–3, 6–3, to give Argentina a 1–0 lead. Argentina went on to win 5–0 to reach the Davis Cup final. Later in the year, Nalbandian reached semifinals at the Masters Series Madrid and the Masters Cup, where he lost to Roger Federer and James Blake, respectively. Despite winning both of his singles rubbers in the Davis Cup final against Safin and Nikolay Davydenko, Nalbandian could not stop the Russian Davis Cup team. Argentina went on to lose 3–2.

2007
2007 saw Nalbandian drop out of the world's top 20 for the first time since 2003, after losing in the fourth round of the 2007 French Open to Nikolay Davydenko. Nalbandian suffered various abdominal injuries, a back injury, and a leg injury during the year. He fell to no. 26 in the world until his season changed after winning the 2007 Madrid Masters. He won the tournament by defeating second seed Rafael Nadal, third seed Novak Djokovic, and top seed Federer in consecutive rounds, becoming the third player after Boris Becker and Djoković to defeat the world's top three players in a single tournament. He defeated Nadal, 6–1, 6–2, in the quarterfinals. His good form carried him to his second top-3 win of the tournament, defeating Djoković in the semifinals. He stunned Federer in the final, 1–6, 6–3, 6–3, and reached the doubles semifinals with Guillermo Cañas in the tournament, before losing to top-seeded brothers Bob and Mike Bryan in the semifinals. After the tournament, his singles ranking moved up from no. 25 on the tour to No. 18. Nalbandian was the only player ever to defeat all 3 members of the big three at the same tournament.

He played at the 2007 Paris Masters and again defeated Federer, in the third round 6–4, 7–6. He beat David Ferrer in the quarterfinals in a closely fought match, 7–6, 6–7, 6–2. After beating Richard Gasquet, 6–2, 6–4 in the semifinals, Nalbandian won his second straight ATP Masters Series title over Rafael Nadal, 6–4, 6–0, thus, becoming the first player to win the Madrid and Paris Masters back to back since former world no. 1, Marat Safin in 2004. This win allowed him to move back into the world's top 10 at No. 9. After the Paris Masters, Nalbandian became the first player to defeat No. 1 and No. 2 players in consecutive tournaments and win them.

2008
Nalbandian began his 2008 season back in the top 10. However, at the Australian Open, he failed to reach the quarterfinals, suffering a 6–1, 6–2, 6–3, loss to the 22nd seed Juan Carlos Ferrero in the third round. On 24 February 2008, he won the Copa Telmex in Buenos Aires, beating José Acasuso, 3–6, 7–6, 6–4, in the final. With that win, he moved to World No. 8. The following week, He arrived at the Abierto Mexicano Telcel in Acapulco, Mexico and cruised all the way to the finals, along the way defeating Boris Pašanski, Santiago Ventura, Potito Starace, and Luis Horna, beating them all in straight sets, but then lost in the final, to Spaniard Nicolás Almagro, 1–6, 6–7.

He entered his first ATP Masters Series tournament of the year at the 2008 Pacific Life Open, and received a bye in the first round because of his seventh seeding. In the second round, he defeated Ernests Gulbis 6–4, 4–6, 7–6, and then came back to beat Radek Štěpánek 7–6, 0–6, 7–6. In the fourth round, he avenged his defeat by beating Juan Carlos Ferrero, to whom he lost earlier in the year at the Australian Open, 6–2, 6–2. He lost, however, in the quarterfinals against Mardy Fish 3–6, 7–6, 6–7, in a very close match. He lost at the Monte Carlo Masters to eventual finalist Federer, 7–5, 2–6, 2–6. In Barcelona, he was the third seed but was eliminated by Stanislas Wawrinka in the third round. At the 2008 Rome Masters, he fell in his opening match to Almagro, 4–6, 5–7.

At the French Open, Nalbandian suffered a shock loss in the second round to Frenchman Jérémy Chardy. After being two sets up and seemingly in control, he lost the next three to hand Chardy the win 6–3, 6–4, 2–6, 1–6, 2–6. He also suffered early exits from both Wimbledon and the US Open, losing in the second round and third round, respectively. His indoor season, however, was a success, as he won his ninth career title at the 2008 Stockholm Open, defeating Robin Söderling 6–2, 5–7, 6–3, in the finals. He was defending champion at the Madrid Masters but was quickly eliminated by fellow Argentine Juan Martín del Potro in the third round. He then entered both the Davidoff Swiss Indoors and the BNP Paribas Masters, where he was once again the defending champion. He did not win either of these tournaments but found himself in the finals of both.

To end the year, he participated in the 2008 Davis Cup and was up on an opening match against David Ferrer. Despite a victory, he ended up on the losing team against Spain in the Davis Cup finals in Argentina (The Argentine team lost 1–3). He made some offensive comments in the press against Spain, the Spanish tennis team, and Rafael Nadal. It was rumoured that he and Agustín Calleri were involved in a fight after they lost their doubles rubber. Nalbandian denied this. He was fined $10,000 for leaving the stadium after his and Calleri's defeat in doubles to Spaniards Fernando Verdasco and Feliciano López, and for his refusal to appear at a subsequent press conference to comment on the Argentine team's setback.

2009
Nalbandian started his 2009 tour by winning his tenth career ATP title at the Medibank International in Sydney, Australia, after defeating Finland's Jarkko Nieminen, 6–3, 6–7, 6–2, in the final. At the Australian Open, he defeated Marc Gicquel in the first round, 6–1, 4–6, 6–2, 6–3, before being upset by unseeded Taiwanese player Lu Yen-Hsun, 4–6, 7–5, 6–4, 4–6, 2–6, in the second round. At the 2009 BNP Paribas Open in Indian Wells, California, he lost to World No. 1 Rafael Nadal, 6–3, 6–7, 0–6, in the fourth round for the first time, failing to convert on five match points in the second set. In May, he announced that he would have to undergo hip surgery, resulting in not being able to compete in the remaining Grand Slams and the Davis Cup. In August, he announced that he would return to practice and eventually to competitive tennis at the Australian Open in January. A few days before the beginning of the tournament, he was forced to withdraw from the event due to an abdominal injury.

2010
Because of several knee injuries in the early part of the 2010 season, he finally made a return, beginning at the 2010 Copa Telmex, his hometown tournament. He beat Potito Starace in the first round 6–2, 7–6, over a period of two days due to a rain delay. In the second round, he beat Daniel Gimeno-Traver 6–7, 6–4, 7–6. However, he pulled out of his quarterfinals match against fifth seed Albert Montañés due to a right leg injury. He made a return to tennis by playing doubles for Argentina in the Davis Cup against Sweden in Stockholm, which he won in straight sets. He played the deciding singles rubber, defeating Vinciguerra 7–5, 6–3, 4–6, 6–4, and helped Argentina reach the quarterfinals.

Playing in his first Masters Series event since Monte Carlo the previous year, he appeared at the 2010 BNP Paribas Open in Indian Wells. There, he won his first-round match against Stefan Koubek, 6–2, 7–6. In his next-round match, he played 22nd seed Jürgen Melzer and lost 4–6, 1–6. He then entered the 2010 Sony Ericsson Open in Miami as a wildcard entrant. He beat Łukasz Kubot 6–3, 6–2, and 30th seed Viktor Troicki 6–3, 4–6, 6–4, before falling to the fourth seed Rafael Nadal in three sets 7–6, 2–6, 2–6. He entered the 2010 Monte-Carlo Rolex Masters in Monaco, ranked No. 151 in the world, beating Andreas Beck in straight sets, before coming through 3–6, 6–4, 7–6 against World No. 13 Mikhail Youzhny of Russia in the second round. Nalbandian beat Tommy Robredo, before losing in the quarterfinals to the second-ranked Novak Djokovic 2–6, 3–6. Nalbandian withdrew from the 2010 Internazionali BNL d'Italia with a right leg injury. The injury persisted, and he withdrew from the 2010 Mutua Madrileña Madrid Open, the 2010 Roland Garros and the  2010 Wimbledon Championships.

In July, he played two singles matches for Argentina against Russia in the Davis Cup at the Olympic Stadium in Moscow. He defeated Nikolay Davydenko, 6–4, 7–6, 7–6, in the first rubber, and Mikhail Youzhny, 7–6, 6–4, 6–3, in the fifth and final rubber, giving Argentina a victory of 3–2 to qualify for the semifinals. He made his return in the 2010 Legg Mason Tennis Classic, where he won the title, his first since 2009 Medibank International Sydney after wins over Rajeev Ram, 6–4, 6–0, Stanislas Wawrinka, 6–3, 6–1, Marco Chiudinelli, 6–1, 6–0, Gilles Simon, 3–6, 6–2, 6–3, and Marin Čilić, 6–2, 6–2. He defeated Marcos Baghdatis in the finals, 6–2, 7–6, guaranteeing a jump in the rankings up to the vicinity of world no. 45. The following week, he had a successful run to the quarterfinals in the Roger's Masters Series in Toronto, defeating David Ferrer, Tommy Robredo, and Robin Söderling, before losing to World No. 4 Andy Murray after this 11-match winning streak. This run took his rank up to world No. 37. He competed at the 2010 BNP Paribas Masters, where he lost again to Murray, 6–2, 4–6, 3–6, in the second round.

In November he was granted the Platinum Konex Award as the best tennis player of the last decade in Argentina.

2011
Nalbandian began the year ranked No. 27 in the world. As sixth seed in the Auckland Open, Nalbandian beat Fabio Fognini, Philipp Kohlschreiber, John Isner, and Nicolás Almagro, without losing a set. However, he lost in the final against David Ferrer. His performance propelled him to the rank of No. 21 in the world, while also achieving the no. 1 Argentina position at the expense of Juan Martín del Potro, who was also injured. He faced Lleyton Hewitt again. The match, dubbed the "Clash of the Titans", went in the fifth set as in 2005, but this time for Nalbandian, after 57 games. He saved two match points, but in the second round was forced to retire due to cramps and fatigue, 1–6, 0–6, 0–2, to Ričardas Berankis. After the Australian Open, he played in the Movistar Open.

He began his tour on clay by beating his compatriot Carlos Berlocq, before losing against Horacio Zeballos. In Buenos Aires, he lost in the quarterfinals to Tommy Robredo. He played a Davis Cup match, winning in four sets against Romanian Adrian Ungur. Due to a torn hamstring and a hernia, he missed many tournaments including Indian Wells, Miami, Monte Carlo, Madrid and Rome Masters. He lost to Roger Federer in the third round of Wimbledon.

2012
In the Australian Open, Nalbandian had a five-set loss to Isner and was fined $8,000 for unsportsmanlike conduct following the match. On February, David participated in two Davis Cup matches for Argentina against the German team, defeating Florian Mayer in a singles match and then partnering with Eduardo Schwank to win a doubles match against Tommy Haas and Philipp Petzschner to help the Argentinian team advance to the quarterfinals. Afterward, Nalbandian played a string of clay tournaments, reaching the quarterfinals in the Brasil Open, semifinals in Buenos Aires and a first-round exit at the Mexican Open. He then entered the first ATP Masters 1000 tournament of the year, the 2012 BNP Paribas Open in Indian Wells, losing in the quarterfinals to Rafael Nadal. After the tournament, Nalbandian reached No. 40 in the ATP rankings but failed to progress past the first round in the 2012 French Open as he was beaten by the Romanian, Adrian Ungur in four sets.

Queen's Club Championships incident
In June, Nalbandian reached the final of the Aegon Championships at the Queen's Club in England for the first time. He led his opponent Marin Čilić by a set but, having been broken to trail 3–4 in the second, was disqualified when he violently kicked a wooden partition in front of a seated line judge, injuring the linesman and drawing blood from his shin.

The kick was broadcast live on the BBC television coverage of the event, and a clip showing the incident was widely viewed on YouTube. A complaint alleging assault was made to the Metropolitan Police, who commenced investigations. An ATP spokesman stated that:"Nalbandian automatically forfeited his prize money and ranking points due to his conduct default. A maximum £8,000 (10,000 euro) fine was issued on site by the ATP Supervisor for unsportsmanlike conduct." In forfeiting his potential prize money of £36,114 [$57,350] plus the £8,000 [$12,560] conduct fine, he incurred a total loss over the weekend of £44,114 [$69,910]. He was additionally docked 150 ranking points by the ATP.

Nalbandian was unseeded at the Wimbledon championships, which followed soon after, and was defeated in straight sets by Janko Tipsarević in the first round. He lost again to Tipsarević in the first round at the London Olympics.

US Open withdrawal
Nalbandian withdrew from the 2012 US Open due to a strained muscle in his chest, one day before his scheduled first-round match against compatriot and 2009 champion Juan Martín del Potro.

2013
He played the last final of his career at the 2013 Brasil Open, where he lost to Rafael Nadal. After the quarterfinal win over France in the Davis Cup, where he played doubles, he was forced to undergo an operation on his right shoulder, sidelining him for much of the 2013 season. On 1 October, he announced his retirement.

After tennis
Nalbandian has sought to continue a sporting career and has taken up Rallying in the Argentine Rally Championship. Since then his career has progressed to appearances in the Codasur South American Rally Championship and one appearance in the World Rally Championship. Mostly he races an Argentine specification Chevrolet Agile.

In February 2021, he has been hired as a coach by Miomir Kecmanović.

Playing style
Nalbandian was an all-court player and a clean ball-striker, hitting powerfully struck groundstrokes. He had a decent, but not particularly dominating service game compared to top 20 players. His signature play was the wide drive that swings out of court on both sides, low and spinning. He could take high balls on the backhand and forehand side and return them with acute angles and low trajectories and used these skills with great tactical intelligence.

His ground game was complemented by his anticipation, speed and ability to end points at the net. Nalbandian's trademark shot is his double-handed backhand down-the-line, which was often regarded as one of the best double-handed backhands on the men's tour. He often used it to set up a point, by either hitting a clean winner or forcing a weak return from the opponent. Nalbandian is also known to be one of the game's best returners. He was consistently able to knock balls back deep on the baseline to effectively set up the point or hit return winners off second serves, but he also had the ability to block it back deep when returning a more effective serve. He also used a "chip-and-charge" technique against the opponents' serves to surprise them.

Early in his career, Nalbandian was considered one of the most talented young players on tour, and touted as a future star of the game, alongside the likes of Roger Federer, Marat Safin and Andy Roddick. Early in his career, he was cited as a rival of Federer, having beaten him five times consecutively between 2002 and 2003. However, injuries, lack of consistency, and poor mental temperament have been cited as his biggest weaknesses that prevented him from achieving his full potential. Nalbandian has been considered by some commentators as one of the biggest underachievers in the game.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: David Nalbandian


text:
Nathaniel de Rothschild

Nathaniel de Rothschild (1812–1870), was a businessman, banker and winemaker. He established the Château Mouton Rothschild.

Early life
Nathaniel de Rothschild was born on 2 July 1812 in London. He was the fourth child of Nathan Mayer Rothschild (1777–1836) and Hannah W. Cohen (1783–1850).

He was a member of the Rothschild banking family of England, closely connected to the Rothschild banking family of France. While he was in his thirties, he was injured in a hunting accident, after which he was rarely seen in public.

Career
He moved to Paris, France in 1850 to work in the banking business owned by his uncle, James Mayer Rothschild (1792–1868).

In 1853, he acquired the Château Brane Mouton, a vineyard in Pauillac in the Gironde département from a Paris banker named Thuret who had previously bought it from Baron Hector de Branne in 1830. Rothschild paid 1,175,000 francs for Brane-Mouton's 65 acres (263,000 m2) of vineyards and renamed the estate, Château Mouton Rothschild. It would become one of the world's best known winemakers.

In 1868, his uncle James acquired the neighboring Château Lafite vineyard. A prestigious first growth (premier cru) property more than three times the size of Chateau Mouton, it created a family rivalry. In the Bordeaux Wine Official Classification of 1855, Château Mouton was ranked second, something that upset its owner a great deal. In response, he composed the motto: Premier ne puis, second ne daigne, Mouton suis. ("First I cannot be, second I do not choose to be, Mouton I am."), a hint on the apocryphal motto of the House of Rohan.

Personal life
In 1842, he married Charlotte de Rothschild (1825–1899), the only daughter of James Mayer Rothschild.. They had the following children:
 * Nathalie de Rothschild (1843–1843)
 * James Edouard de Rothschild (1844–1881), married Laura Thérèse von Rothschild (m. 1871)
 * Mayer Albert de Rothschild (1846–1850)
 * Arthur de Rothschild (1851–1903)

In 1856, Nathaniel and his wife purchased the property at 33 Rue du Faubourg Saint-Honoré in Paris from Denis, duc Decrès. At the time it was rented to the Russian Embassy but when the lease ran out in 1864, he renovated the building and made it his city residence. Passed down to his son Arthur de Rothschild, he sold it in 1918 to the Cercle de l'Union interalliée. In 1878, Nathaniel bought the Abbaye des Vaux de Cernay in Cernay-la-Ville in the Vallée de Chevreuse, at the time only a ruins of a Cistercian abbey built in 1118. He and his wife undertook extensive restoration work and new construction to turn the lakeside property into a luxurious country home.

The property of Château Mouton Rothschild will pass to his son James Nathan and through him, to his great grandson Philippe de Rothschild

Death and legacy
He died on 19 February 1870 in Paris, France.

After his death, his children and grandchildren showed little enthusiasm for the wine business. It would be 118 years later before Château Mouton, under the leadership of Nat's great-grandson Philippe de Rothschild (1902–88), would become the only French vineyard to ever achieve reclassification to First Growth.

title: Nathaniel de Rothschild


text:
Calormen

In C. S. Lewis's Chronicles of Narnia series of novels, Calormen is a large country to the southeast of Narnia. Lewis probably derived its name from the Latin calor, meaning "heat". When using the name as an adjective or an ethnonym, Lewis spelled the name with an 'e' at the end: a Calormene soldier; "The Calormenes have dark faces and long beards."

Narnia and Calormen are separated by the country of Archenland and a large desert. In The Horse and His Boy, Calormen is described as being many times the size of its northern neighbours, and it is implied that its army is always either conquering more land or keeping down rebellions, in wars with which neither Narnia nor Archenland are involved. The border of the Calormene Empire extends from the Western Mountains to the Great Eastern Ocean. The Calormene capital is Tashbaan, a large walled city located on an island hill at the mouth of a river and close to the northern desert.

History
The country of Calormen was first mentioned by Lewis in a passing reference in chapter 2 of Prince Caspian, though in the first edition it was spelt Kalormen. He first wrote about Calormene characters in the subsequent Voyage of the Dawn Treader, though neither of these is their first chronological appearance in the series. They are presented with the following words: "The Calormenes have dark faces and long beards. They wear flowing robes and orange-coloured turbans, and they are a wise, wealthy, courteous, cruel and ancient people". As narrated in that book, after the Telmarine kings cut Narnia off from the sea, the Lone Islands—though in theory remaining a Narnian possession—fell into the Calormene sphere of influence, becoming a major source of slaves for Calormen and adopting the Calormene Crescent as the islands' currency. After Caspian the Seafarer restored Narnian rule and abolished slavery in the islands, there was some apprehension of Calormen resorting to war to regain its influence there. The book's plot then moves away and it remains unknown whether such a war took place. However, Lewis later placed Calormen at the focus of The Horse and His Boy—set a thousand years earlier, at the time of High King Peter.

The origins of Calormen and the Calormenes are not made clear during the Chronicles. According to the Narnian timeline published by Walter Hooper, Calormen was founded by Archen outlaws, who traveled over the Great Desert to the south some 24 years after Archenland's founding. In an alternative theory, Calormen was founded by people accidentally crossing into Calormen from our world through a Middle Eastern portal (similar to the English wardrobe in The Lion, The Witch and the Wardrobe), which was subsequently lost or destroyed, preventing their return. The Calormenes speak a flowery version of the standard English favoured by both human and animal Narnians, which might support this argument; however, Jadis also speaks English. The reason for the ancient Persian, Moorish, Mughal, Indian and Ottoman Turkish aspects of Calormene culture, or the origin of their religion, was not satisfactorily explained, but stand in strong counterpoint to the largely European, Anglo and Greco-Roman (and Christian) aspects of Narnia and Archenland.

Throughout the times covered by the Chronicles of Narnia, Calormen and Narnia maintain an uneasy, albeit generally peaceable, coexistence. The Horse and His Boy and The Last Battle contain plot lines that focus on Calormen, while some of the other books have peripheral references. In The Horse and His Boy the main characters (one a young member of the Calormene nobility) escape from Calormen to Archenland and Narnia whilst the Calormene cavalry under Prince Rabadash attempts to invade Narnia and capture the Narnian Queen Susan for his bride. The rather small (200 horse) Calormene invasion force is rebuffed at the gates of the Kingdom of Archenland. In The Last Battle, there is a reference to King Erlian having fought a war with the Calormenes. King Tirian is—until the events narrated in the book—at peace with them, and some level of trade and travel exist between Narnia and Calormen. The Narnian King maintains a supply of Calormene armour and weapons for the purpose of conducting undercover operations in their country—suggesting a kind of cold war.

Calormenes are described as dark-skinned, with the men mostly bearded. Flowing robes, turbans and wooden shoes with an upturned point at the toe are common items of clothing, and the preferred weapon is the scimitar. Lavish palaces are present in the Calormene capital Tashbaan. The overall leitmotif of Calormene culture is portrayed as ornate to the point of ostentation. The people of Calormen are concerned with maintaining honour and precedent, often speaking in maxims and quoting their ancient poets. Veneration of elders and absolute deference to power are marks of Calormene society. Power and wealth determine class and social standing, and slavery is commonplace. The unit of currency is the Crescent. Narnians hold Calormenes in disdain for their treatment of animals and slaves. Conversely, Calormenes refer to the human inhabitants of Narnia as "barbarians". All of this appears quite consistent with the Osmanli Turkish Ottoman Empire (1299-1923), its known and purported splendor, rigid class structure, and the always-volatile relationship with many of its European neighbors.

The ruler of Calormen is called the Tisroc and is believed by the Calormene people to have descended in a direct line from the god Tash, whom the people worship in addition to other gods and goddesses. The illustrations of Tash, a vulture headed god, by Pauline Baynes appear to be inspired by Hindu as opposed to Islamic imagery, with multiple arms and a distinct resemblance to the ancient Indian deity Garuda. Calormenes always follow a mention of the Tisroc with the phrase "may he live forever". Ranking below the Tisroc are his sons (princes), a Grand Vizier, and the noble classes, who are addressed as Tarkaan (male) and Tarkheena (female). The nobility have a band of gold on their arm and their marriages are usually arranged at a young age. Beneath them are soldiers of the empire's vast army, merchants, and the peasantry, with slaves being the lowest rung on the social ladder. The Calormene leaders are portrayed as quite war-like, and the Tisrocs generally seem to have a wish to conquer the "barbarian" lands to their north - to some degree deterred, however, by the magical reputation of the countries, their various rulers and their being known to be under the protection of Aslan. Significantly, the final, successful invasion of Narnia by the Calormene military, which precipitates the end of the Narnian universe, was conducted in close cooperation with the appearance of the false Aslan and the proclamation that Aslan and Tash are one and the same.

Calormene social and political institutions are depicted as essentially unchanged between the time of The Horse and His Boy and The Last Battle—more than a thousand years, in which Narnia has profoundly changed several times. This is clearly an artifact of the order in which C. S. Lewis wrote and published the stories, with the two stories above and The Magician's Nephew which also references ancient Mesopotamian civilisation in its depiction of Queen Jadis and Charn, appearing last three of the seven.

When at the end of The Last Battle the characters cross into the Real Narnia and find there the counterparts of all the places they had known in the destroyed Narnia, there is a reference to a counterpart of Calormen being also there to its south, complete with the capital Tashbaan—presumably without the nastier aspects of Calormene culture, but this is not discussed in detail.

Tashbaan
The capital of Calormen is the walled city of Tashbaan, situated on a river mouth located on the southern verge of the great desert dividing the empire from the northern states of Narnia and Archenland.

Tashbaan is described as one of the wonders of the world. The city is a hot and crowded place, though with fine streets, magnificent palaces, and gardens. It is built on a natural slope, rising to the palace of the Tisroc and the great Temple of Tash at the pinnacle of the hill. The palace of the Tisroc is referred to as being magnificent beyond description and opens onto gardens that run right down to the river wall. Tashbaan is surrounded by a strong wall that rises out of the water and is reached by long bridges from both banks, providing the only place where crossing the great river of Calormen is possible for many miles. The banks of the river are lined with gardens and country houses. The Tombs of the Ancient Kings, believed by the Carlomenes to be haunted, lie directly across the river from Tashbaan, on the edge of the desert.

Calormene Poetry
The poetry of Calormen is prolix, sententious, and moralizing. Quotations from Calormen poets are often quoted as proverbs. These include such as the following: "Application to business is the root of prosperity but those who ask questions that do not concern them are steering the ship of folly towards the rock of indigence. Natural affection is stronger than soup and offspring more precious than carbuncles. He who attempts to deceive the judicious is already baring his back for the scourge.  Swords can be kept off with shields but the Eye of Wisdom pierces through every defence.  Deep draughts from the fountain of reason are desirable in order to extinguish the fire of youthful love."

Calormenes disparage Narnian poetry, contending that it is all about things like love and war and not about useful maxims, but when the Calormen-raised Cor and Aravis first hear Narnian (or Cor's native Archenlandish) poetry they find it much more exciting. Calormen also prizes the art of story-telling, which, according to Lewis, forms part of the education of the nobility. The talking horse Bree, though not fond of most things Calormene, thoroughly enjoys a story told in Calormene style by Aravis. He also has the habit of rolling like inarticulate Calormene horses.

Concepts of freedom and slavery
In The Horse and His Boy, Lewis uses the cultural settings of Narnia, Archenland, and Calormen to develop a theme of freedom in contrast to slavery. Lewis depicts the Calormene culture as one in which a primary guiding principle is that the weak must make way for the strong: "For in Tashbaan there is only one traffic regulation, which is that everyone who is less important has to get out of the way for everyone who is more important; unless you want a cut from a whip or a punch from the butt end of a spear." He also reveals the motivation for Calormene attempts to invade Archenland and, ultimately, Narnia, as a refusal to abide the thought of free countries so close to the border of the Calormene empire, as illustrated by this speech given by the Tisroc: "'These little barbarian countries that call themselves free (which is as much to say, idle, disordered, and unprofitable) are hateful to the gods and to all persons of discernment.'" In contrast, the kings and queens of Narnia and Archenland, as rulers of free people, hold themselves responsible for the well-being of their subjects. As King Lune tells Shasta/Cor: "'For this is what it means to be a king: to be first in every desperate attack and last in every desperate retreat, and when there's hunger in the land (as must be now and then in bad years) to wear finer clothes and laugh louder over a scantier meal than any man in your land.'"

Accusations of racism
C. S. Lewis has been accused of racism, particularly in his depiction of the Calormenes. In the Companion to Narnia, the Catholic theologian Paul F. Ford wrote "C. S. Lewis was a man of his time and socioeconomic class. Like many English men of this era, Lewis was unconsciously but regrettably unsympathetic to things and people Middle Eastern. Thus he sometimes engages in exaggerated stereotyping in contrasting things Narnian and things Calormene. He intends this in a broadly comic way, almost vaudevillian. But in our post-September 11, 2001, world, he would, I am sure, want to reconsider this insensitivity." Outspoken atheist critic and novelist Philip Pullman has called the Chronicles of Narnia "blatantly racist" and in an interview with The Observer, criticised the film adaptation of The Lion, the Witch and the Wardrobe by saying the books contained "a peevish blend of racist, misogynistic, and reactionary prejudice".

Calormenes live south of a desert, wear turbans and pointed shoes, their noblemen are called Tarkaans (similar to the medieval Central Asian title tarkhan), they are armed with scimitars, and their money is called "crescents".

Of Lewis, Kyrie O'Connor writes: "In his time, people thought it was amusing to make fun of other cultures. We don't. Read the stories, ask questions, and remember that the person who wrote this story was altogether too human." Claims of racism can be seen as countered by Lewis's positive portrayal of two Calormenes and the lack of racism shown to them by Narnian nobility. Lewis writes in The Last Battle that those who worship Tash and who are virtuous are in fact worshipping Aslan, and those who are immoral and who worship Aslan are in fact worshipping Tash: "I and [Tash] are of such different kinds that no service which is vile can be done to me, and none which is not vile can be done to him."

In foreign languages
In the Russian translation of the Narnia books, Calormen is known as "Tarkhistan" (Тархистан), as a reference to the Tarkaan nobles and its Turkish and Persian cultural influences.

title: Calormen


text:
Cycle detection

In computer science, cycle detection or cycle finding is the algorithmic problem of finding a cycle in a sequence of iterated function values.

For any function $f$ that maps a finite set $S$ to itself, and any initial value $x_{0}$ in $S$, the sequence of iterated function values

 * $$ x_0,\ x_1=f(x_0),\ x_2=f(x_1),\ \dots,\ x_i=f(x_{i-1}),\ \dots$$

must eventually use the same value twice: there must be some pair of distinct indices $i$ and $j$ such that $x_{i} = x_{j}$. Once this happens, the sequence must continue periodically, by repeating the same sequence of values from $x_{i}$ to $x_{j − 1}$. Cycle detection is the problem of finding $i$ and $j$, given $f$ and $x_{0}$.

Several algorithms are known for finding cycles quickly and with little memory. Robert W. Floyd's tortoise and hare algorithm moves two pointers at different speeds through the sequence of values until they both point to equal values. Alternatively, Brent's algorithm is based on the idea of exponential search. Both Floyd's and Brent's algorithms use only a constant number of memory cells, and take a number of function evaluations that is proportional to the distance from the start of the sequence to the first repetition. Several other algorithms trade off larger amounts of memory for fewer function evaluations.

The applications of cycle detection include testing the quality of pseudorandom number generators and cryptographic hash functions, computational number theory algorithms, detection of infinite loops in computer programs and periodic configurations in cellular automata, automated shape analysis of linked list data structures, and detection of deadlocks for transactions management in DBMS.

Example
The figure shows a function $f$ that maps the set $S = {0,1,2,3,4,5,6,7,8}$ to itself. If one starts from $x_{0} = 2$ and repeatedly applies $f$, one sees the sequence of values

The cycle in this value sequence is $2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1, ....$.

Definitions
Let $S$ be any finite set, $f$ be any function from $S$ to itself, and $6, 3, 1$ be any element of $S$. For any $x_{0}$, let $i > 0$. Let $μ$ be the smallest index such that the value $x_{i} = f(x_{i − 1})$ reappears infinitely often within the sequence of values $x_{μ}$, and let $λ$ (the loop length) be the smallest positive integer such that $x_{i}$. The cycle detection problem is the task of finding $λ$ and $μ$.

One can view the same problem graph-theoretically, by constructing a functional graph (that is, a directed graph in which each vertex has a single outgoing edge) the vertices of which are the elements of $S$ and the edges of which map an element to the corresponding function value, as shown in the figure. The set of vertices reachable from starting vertex $x_{μ} = x_{λ + μ}$ form a subgraph with a shape resembling the Greek letter rho ($ρ$): a path of length $μ$ from $x_{0}$ to a cycle of $λ$ vertices.

Computer representation
Generally, $f$ will not be specified as a table of values, the way it is shown in the figure above. Rather, a cycle detection algorithm may be given access either to the sequence of values $x_{0}$, or to a subroutine for calculating $f$. The task is to find $λ$ and $μ$ while examining as few values from the sequence or performing as few subroutine calls as possible. Typically, also, the space complexity of an algorithm for the cycle detection problem is of importance: we wish to solve the problem while using an amount of memory significantly smaller than it would take to store the entire sequence.

In some applications, and in particular in Pollard's rho algorithm for integer factorization, the algorithm has much more limited access to $S$ and to $f$. In Pollard's rho algorithm, for instance, $S$ is the set of integers modulo an unknown prime factor of the number to be factorized, so even the size of $S$ is unknown to the algorithm. To allow cycle detection algorithms to be used with such limited knowledge, they may be designed based on the following capabilities. Initially, the algorithm is assumed to have in its memory an object representing a pointer to the starting value $x_{i}$. At any step, it may perform one of three actions: it may copy any pointer it has to another object in memory, it may apply $f$ and replace any of its pointers by a pointer to the next object in the sequence, or it may apply a subroutine for determining whether two of its pointers represent equal values in the sequence. The equality test action may involve some nontrivial computation: for instance, in Pollard's rho algorithm, it is implemented by testing whether the difference between two stored values has a nontrivial greatest common divisor with the number to be factored. In this context, by analogy to the pointer machine model of computation, an algorithm that only uses pointer copying, advancement within the sequence, and equality tests may be called a pointer algorithm.

Algorithms
If the input is given as a subroutine for calculating $f$, the cycle detection problem may be trivially solved using only $x_{0}$ function applications, simply by computing the sequence of values $λ + μ$ and using a data structure such as a hash table to store these values and test whether each subsequent value has already been stored. However, the space complexity of this algorithm is proportional to $x_{i}$, unnecessarily large. Additionally, to implement this method as a pointer algorithm would require applying the equality test to each pair of values, resulting in quadratic time overall. Thus, research in this area has concentrated on two goals: using less space than this naive algorithm, and finding pointer algorithms that use fewer equality tests.

Floyd's tortoise and hare
Floyd's cycle-finding algorithm is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds. It is also called the "tortoise and the hare algorithm", alluding to Aesop's fable of The Tortoise and the Hare.

The algorithm is named after Robert W. Floyd, who was credited with its invention by Donald Knuth. However, the algorithm does not appear in Floyd's published work, and this may be a misattribution: Floyd describes algorithms for listing all simple cycles in a directed graph in a 1967 paper, but this paper does not describe the cycle-finding problem in functional graphs that is the subject of this article. In fact, Knuth's statement (in 1969), attributing it to Floyd, without citation, is the first known appearance in print, and it thus may be a folk theorem, not attributable to a single individual.

The key insight in the algorithm is as follows. If there is a cycle, then, for any integers $λ + μ$ and $i ≥ μ$, $k ≥ 0$, where $λ$ is the length of the loop to be found, $μ$ is the index of the first element of the cycle, and $k$ is a whole integer representing the number of loops. Based on this, it can then be shown that $x_{i} = x_{i + kλ}$ for some $i = kλ ≥ μ$ if and only if $k$ (if $x_{i} = x_{2i}$ in the cycle, then there exists some $k$ such that $x_{i} = x_{2i}$, which implies that $2i = i + kλ$; and if there are some $i$ and $k$ such that $i = kλ$, then $i = kλ$ and $2i = i + kλ$). Thus, the algorithm only needs to check for repeated values of this special form, one twice as far from the start of the sequence as the other, to find a period $ν$ of a repetition that is a multiple of $λ$. Once $ν$ is found, the algorithm retraces the sequence from its start to find the first repeated value $x_{2i} = x_{i + kλ}$ in the sequence, using the fact that $λ$ divides $ν$ and therefore that $x_{μ}$. Finally, once the value of $μ$ is known it is trivial to find the length $λ$ of the shortest repeating cycle, by searching for the first position $x_{μ} = x_{μ + v}$ for which $μ + λ$.

The algorithm thus maintains two pointers into the given sequence, one (the tortoise) at $x_{μ + λ} = x_{μ}$, and the other (the hare) at $x_{i}$. At each step of the algorithm, it increases $i$ by one, moving the tortoise one step forward and the hare two steps forward in the sequence, and then compares the sequence values at these two pointers. The smallest value of $x_{2i}$ for which the tortoise and hare point to equal values is the desired value $ν$.

The following Python code shows how this idea may be implemented as an algorithm.

This code only accesses the sequence by storing and copying pointers, function evaluations, and equality tests; therefore, it qualifies as a pointer algorithm. The algorithm uses $i > 0$ operations of these types, and $O(λ + μ)$ storage space.

Brent's algorithm
Richard P. Brent described an alternative cycle detection algorithm that, like the tortoise and hare algorithm, requires only two pointers into the sequence. However, it is based on a different principle: searching for the smallest power of two $O(1)$ that is larger than both $λ$ and $μ$. For $2^{i}$, the algorithm compares $i = 0, 1, 2, ...$ with each subsequent sequence value up to the next power of two, stopping when it finds a match. It has two advantages compared to the tortoise and hare algorithm: it finds the correct length $λ$ of the cycle directly, rather than needing to search for it in a subsequent stage, and its steps involve only one evaluation of the function $f$ rather than three.

The following Python code shows how this technique works in more detail.

Like the tortoise and hare algorithm, this is a pointer algorithm that uses $x_{2^{i}−1}$ tests and function evaluations and $O(λ + μ)$ storage space. It is not difficult to show that the number of function evaluations can never be higher than for Floyd's algorithm. Brent claims that, on average, his cycle finding algorithm runs around 36% more quickly than Floyd's and that it speeds up the Pollard rho algorithm by around 24%. He also performs an average case analysis for a randomized version of the algorithm in which the sequence of indices traced by the slower of the two pointers is not the powers of two themselves, but rather a randomized multiple of the powers of two. Although his main intended application was in integer factorization algorithms, Brent also discusses applications in testing pseudorandom number generators.

Gosper's algorithm
R. W. Gosper's algorithm finds the period $$\lambda$$, and the lower and upper bound of the starting point, $$\mu_l$$ and $$\mu_u$$, of the first cycle. The difference between the lower and upper bound is of the same order as the period, i.e. $$\mu_l + \lambda \sim \mu_h$$.

Advantages
The main feature of Gosper's algorithm is that it never backs up to reevaluate the generator function, and is economical in both space and time. It could be roughly described as a concurrent version of Brent's algorithm. While Brent's algorithm gradually increases the gap between the tortoise and hare, Gosper's algorithm uses several tortoises (several previous values are saved), which are roughly exponentially spaced. According to the note in HAKMEM item 132, this algorithm will detect repetition before the third occurrence of any value, i.e. the cycle will be iterated at most twice. This note also states that it is sufficient to store $$\Theta(\log \lambda)$$ previous values; however, the provided implementation stores $$\Theta(\log (\mu + \lambda))$$ values. For example, assume the function values are 32-bit integers and the second iteration of the cycle ends after at most 232 function evaluations since the beginning (viz. $$\mu + 2\lambda \le 2^{32}$$). Then Gosper's algorithm will find the cycle after at most 232 function evaluations, while consuming the space of 33 values (each value being a 32-bit integer).

Complexity
Upon the $$i$$-th evaluation of the generator function, the algorithm compares the generated value with $$O(\log i)$$ previous values; observe that $$i$$ goes up to at least $$\mu + \lambda$$ and at most $$\mu + 2\lambda$$. Therefore, the time complexity of this algorithm is $$O((\mu + \lambda) \cdot \log (\mu + \lambda))$$. Since it stores $$\Theta(\log (\mu + \lambda))$$ values, its space complexity is $$\Theta(\log (\mu + \lambda))$$. This is under the usual assumption, present throughout this article, that the size of the function values is constant. Without this assumption, the space complexity is $$\Omega(\log^2 (\mu + \lambda))$$ since we need at least $$\mu + \lambda$$ distinct values and thus the size of each value is $$\Omega(\log (\mu + \lambda))$$.

Time–space tradeoffs
A number of authors have studied techniques for cycle detection that use more memory than Floyd's and Brent's methods, but detect cycles more quickly. In general these methods store several previously-computed sequence values, and test whether each new value equals one of the previously-computed values. In order to do so quickly, they typically use a hash table or similar data structure for storing the previously-computed values, and therefore are not pointer algorithms: in particular, they usually cannot be applied to Pollard's rho algorithm. Where these methods differ is in how they determine which values to store. Following Nivasch, we survey these techniques briefly.

 * Brent already describes variations of his technique in which the indices of saved sequence values are powers of a number $R$ other than two. By choosing $R$ to be a number close to one, and storing the sequence values at indices that are near a sequence of consecutive powers of $R$, a cycle detection algorithm can use a number of function evaluations that is within an arbitrarily small factor of the optimum $O(1)$.
 * Sedgewick, Szymanski, and Yao provide a method that uses $M$ memory cells and requires in the worst case only $$(\lambda+\mu)(1+cM^{-1/2})$$ function evaluations, for some constant $c$, which they show to be optimal. The technique involves maintaining a numerical parameter $d$, storing in a table only those positions in the sequence that are multiples of $d$, and clearing the table and doubling $d$ whenever too many values have been stored.
 * Several authors have described distinguished point methods that store function values in a table based on a criterion involving the values, rather than (as in the method of Sedgewick et al.) based on their positions. For instance, values equal to zero modulo some value $d$ might be stored. More simply, Nivasch credits D. P. Woodruff with the suggestion of storing a random sample of previously seen values, making an appropriate random choice at each step so that the sample remains random.
 * Nivasch describes an algorithm that does not use a fixed amount of memory, but for which the expected amount of memory used (under the assumption that the input function is random) is logarithmic in the sequence length. An item is stored in the memory table, with this technique, when no later item has a smaller value. As Nivasch shows, the items with this technique can be maintained using a stack data structure, and each successive sequence value need be compared only to the top of the stack. The algorithm terminates when the repeated sequence element with smallest value is found. Running the same algorithm with multiple stacks, using random permutations of the values to reorder the values within each stack, allows a time–space tradeoff similar to the previous algorithms. However, even the version of this algorithm with a single stack is not a pointer algorithm, due to the comparisons needed to determine which of two values is smaller.

Any cycle detection algorithm that stores at most $M$ values from the input sequence must perform at least $$(\lambda+\mu)\left(1+\frac{1}{M-1}\right)$$ function evaluations.

Applications
Cycle detection has been used in many applications.
 * Determining the cycle length of a pseudorandom number generator is one measure of its strength. This is the application cited by Knuth in describing Floyd's method. Brent describes the results of testing a linear congruential generator in this fashion; its period turned out to be significantly smaller than advertised. For more complex generators, the sequence of values in which the cycle is to be found may not represent the output of the generator, but rather its internal state.
 * Several number-theoretic algorithms are based on cycle detection, including Pollard's rho algorithm for integer factorization and his related kangaroo algorithm for the discrete logarithm problem.
 * In cryptographic applications, the ability to find two distinct values xμ−1 and xλ+μ−1 mapped by some cryptographic function ƒ to the same value xμ may indicate a weakness in ƒ. For instance, Quisquater and Delescaille apply cycle detection algorithms in the search for a message and a pair of Data Encryption Standard keys that map that message to the same encrypted value; Kaliski, Rivest, and Sherman also use cycle detection algorithms to attack DES. The technique may also be used to find a collision in a cryptographic hash function.
 * Cycle detection may be helpful as a way of discovering infinite loops in certain types of computer programs.
 * Periodic configurations in cellular automaton simulations may be found by applying cycle detection algorithms to the sequence of automaton states.
 * Shape analysis of linked list data structures is a technique for verifying the correctness of an algorithm using those structures. If a node in the list incorrectly points to an earlier node in the same list, the structure will form a cycle that can be detected by these algorithms. In Common Lisp, the S-expression printer, under control of the  variable, detects circular list structure and prints it compactly.
 * Teske describes applications in computational group theory: determining the structure of an Abelian group from a set of its generators. The cryptographic algorithms of Kaliski et al. may also be viewed as attempting to infer the structure of an unknown group.
 * briefly mentions an application to computer simulation of celestial mechanics, which she attributes to William Kahan. In this application, cycle detection in the phase space of an orbital system may be used to determine whether the system is periodic to within the accuracy of the simulation.
 * In Mandelbrot Set fractal generation some performance techniques are used to speed up the image generation. One of them is called "period checking", which consists of finding the cycles in a point orbit. This article describes the "period checking" technique. You can find another explanation here. Some cycle detection algorithms have to be implemented in order to implement this technique.

title: Cycle detection


text:
Talk:List of highest elevations of U.S. states

Connecticut and Frissell/Bear
I think that Bear Mountain is a more appropriate "tallest mountain of Connecticut", since Frissell Mountain's peak is not in Connecticut. I don't feel extremely strongly about this, though. - Plutor 18:28, 21 May 2004 (UTC)


text:
Jefferson Academy

Jefferson Academy may refer to:

 * Jefferson Academy Charter School, a charter school in Jefferson County, Colorado
 * Jefferson Academy (Monticello, Florida), a former school
 * Martin Institute, formerly known as Jefferson Academy in Jefferson, Georgia
 * Vincennes University, a university in Vincennes, Indiana formerly known as Jefferson Academy

title: Jefferson Academy


text: User talk:216.61.124.89

title: User talk:216.61.124.89


text:
Lambert Cadwalader (representative)

Lambert Cadwalader (December 1742 – September 13, 1823) was an American merchant and leader in New Jersey and Pennsylvania. He fought in the Revolutionary War, then represented New Jersey in the Continental Congress and the U.S. Congress.

Early life
Lambert was born in Trenton, New Jersey, to Doctor Thomas and Hannah (née Lambert) Cadwalader. By 1750, his family had returned to Philadelphia, Pennsylvania, where he attended Dr. Allison's Academy.

In 1757, he entered the College of Philadelphia (later the University of Pennsylvania), but did not graduate. Instead, he went into business with his brother John Cadwalader.

Career
The brothers' business was a success and they became more active in civic affairs, both in Philadelphia and the wider field of the colony of Pennsylvania. They signed the non-importation agreement in 1765, to support the boycott of English merchants. Lambert became a particularly outspoken opponent of the Stamp Act and later measures. In 1768 he was elected to the American Philosophical Society. In 1774, he has elected to the Provincial Assembly, and, in Philadelphia, he was appointed to the city's Committee of Correspondence.

Revolutionary years
In 1775, Lambert returned again to the colonial Assembly. He also advanced in the militia, and was named captain of one of the companies raised in the city. Then, in the spring of 1776, he played a prominent role in the call for a state Constitutional Convention. He was named as a delegate, but attended only the first few meetings, as military duty called him away.

In January 1776, Cadwalader had been promoted to lieutenant colonel of the 3rd Pennsylvania Battalion of the Continental Army. Late in the summer, he was in New York to aid that city's defense. He began work on building the defenses at Fort Washington in August. After the Battle of Brooklyn, he worked with George Washington to set up defenses on the Brooklyn Heights, but they were forced to withdraw to Manhattan on August 30, because the British had overwhelming numbers.

The 3rd Pennsylvania returned to the defense of Fort Washington. At the beginning of the battle for the Fort, on November 15, Cadwalader was holding the old line on the Harlem Heights. Facing two British regiments, with three more landed to their rear, the Americans were forced to withdraw to the fort. When Colonel Magaw surrendered the fort on the next day, Cadwalader was among those taken prisoner. He was soon released, after giving his parole to British General Howe. Lambert's quick release was partly due to the consideration that his father, Dr. Thomas Cadwalader, had shown to General Richard Prescott as a prisoner of war in Philadelphia in 1776.

Early in 1777, Cadwalader was named colonel and commander of the 3rd Battalion, now called the 4th Pennsylvania Regiment. He declined to take up the assignment because he was on parole and could not serve until exchanged. He was carried on the rolls for almost two years, but a suitable exchange was never arranged. Finally, after officer exchanges broke down, Washington accepted his resignation on January 29, 1777.

When the British occupied Philadelphia in 1777, he withdrew to his father's property near Trenton, New Jersey. This home, called "Greenwood", would be his residence for the rest of his life.

Later life
In 1784, New Jersey selected him as a delegate to the Continental Congress. He would serve there for the remaining life of that institution, being returned each year until 1787. When the new government was established for the United States, Cadwalader was a Federalist in national politics. He was elected to the U.S. Congress twice, in 1788 and 1792.

Although eligible, Cadwalader did not join The Society of the Cincinnati as an original member when it was established in 1783. He did however qualify for membership and became eligible for representation by a living descendant after the "Rule of 1854" was adopted by the Society as a way to revive the membership.

Personal life
In 1793, in his early 50s, Cadwalader married Mary McCall (1764–1848), the daughter of Archibald and Judith (née Kemble) McCall. They had one child:

 * Thomas McCall Cadwalader (1795–1873), who married Maria Charlotte Gouverneur (1801–1867). Maria was the sister of Samuel Laurence Gouverneur (1799–1865) and the niece of Elizabeth Kortright and U.S. President James Monroe.

He died at Greenwood, in Trenton, Mercer County, New Jersey on September 13, 1823, and is buried in the Friends Burying Ground at Trenton.

title: Lambert Cadwalader (representative)


text:
Ape (disambiguation)

Apes are anthropoids of the Hominoidea superfamily.

Ape or APE may also refer to:

People

 * Ape, an alias of the 19th century artist Carlo Pellegrini (1839–1889)
 * Keith Ape, South Korean rapper

Fictional characters

 * Ape, a fictional character from the George of the Jungle franchise
 * Ape (comics), a mutant character in the Marvel Comics universe

Places

 * Ape, Latvia, town in Latvia
 * Ape Parish, Ape Municipality, Latvia
 * Ape Canyon, Plains of Abraham, Mount St. Helens, Washington, USA
 * Ape Hill, Shoushan, Kaohsiung, Taiwan

Science and technology

 * Ape (plant), the Polynesian name for the giant taro plant
 * Xanthosoma ('ape), tropical American plant
 * Acute pulmonary edema, fluid accumulation on the lungs
 * Anomalous photovoltaic effect, a type of a photovoltaic effect which occurs in semiconducting materials
 * AP Environmental Science, the environmental science course in the Advanced Placement program
 * Available potential energy, or convective available potential energy, the energy a parcel of air would have if lifted through the atmosphere

Computing

 * AJAX Push Engine, an open source Comet/push server
 * ANSI/POSIX Environment, a POSIX compatibility layer for the Plan 9 operating system
 * APE tag, a tag format used to add metadata to digital audio files
 * .ape, a filename extension used by Monkey's Audio
 * APE100, a series of Italian supercomputers
 * Application Enhancer, a product by Unsanity
 * AVS plugin effect, any third-party addition to the Advanced Visualization Studio computer software
 * Auckland Peering Exchange, a peering point serving Auckland, New Zealand

Arts and entertainment

 * Agency to Prevent Evil, a fictional agency in Lancelot Link, Secret Chimp
 * Animals project editor in the computer game Zoo Tycoon
 * APE Con or Alternative Press Expo, an annual comics convention
 * "The Ape", a song by Level 42 on the album Guaranteed
 * The Apes, a band from Washington, D.C.

Films

 * The Ape (1940 film) starring Boris Karloff
 * Ape (1976 film)
 * The Ape (2005 film)
 * The Ape (2009 film), a Swedish film
 * Ape (2012 film)

Transportation

 * Piaggio Ape, a small Italian tricycle pickup-truck
 * Honda Ape, a Japanese minibike
 * APE 4.80, a passenger trailer for the road

Other uses

 * Adapted physical education, for learners with a disability
 * Annual premium equivalent, a measure used for comparison of life insurance revenue
 * APE Foundation (Association for the Protection of the Environment)
 * APE, a stock market ticker for AMC Theatres, an American movie theater chain
 * Ape, Inc., a video game development company
 * Bukiyip language of Papua New Guinea (ISO 639 code: ape)

title: Ape (disambiguation)


text:
Talk:Cycle detection

Other
Sorry about the mistake in the image - lambda should be 2 (the number of elements not involved in the cycle). I uploaded (and re-uploaded) a fixed image, but it doesn't seem to have taken effect. I tried emptying my cache, but the old, incorrect image is still there. Also, the new image has labels on the elements. I'll give it a few hours, and if it still hasn't worked I'm re-uploading again. --Decrypt3 18:38, May 21, 2004 (UTC)

Fixed it by re-uploading under a different name. Any sysops who see this should delete CycleFinding.Dec3.png. --Decrypt3 12:29, May 22, 2004 (UTC)

Contradictions in the article
The article states that the worst-case performance of the algorithm is λ + μ/2 comparisons. This statement cannot be correct, since in the example where λ=2 and μ=6, λ + μ/2 = 5, but the description of a running of the algorithm states that it finishes in 6 iterations.

The article also states that the slow sequence cannot get more than halfway around the loop without meeting the fast sequence, but in the given example the sequences meet at the second half of the loop.

 * Fixed. BradAustin2 21:55, 11 March 2007 (UTC)

Reference for the algorithm
The article in JACM cited:

 * {cite journal|last=Floyd|first=R.W.|authorlink=Robert W. Floyd|title=Non-deterministic Algorithms|journal=J. ACM|pages=pp. 636-644|month=October|year=1967|url=http://doi.acm.org/10.1145/321420.321422}

does in fact contain a cycle-finding algorithm, but it's a backtracking algorithm for finding all cycles in a graph of a bounded size (essentially depth-first search). It's not the tortoise-and-hare algorithm. I'm intrigued that a little Googling for citations finds only references to the same JACM paper. Is there a published source of the original algorithm, or are we all relying on folk-knowledge that this was first published by Floyd? —Preceding unsigned comment added by 163.1.125.59 (talk) 10:56, 16 October 2007 (UTC)

Don Knuth's Art of Computer Programming, Vol 2 (Seminumerical Algorithms) attributes the idea to Bob Floyd, and has the algorithm in the exercises. That dates it to about 1968, but does not give a published reference.163.1.125.59 13:38, 16 October 2007 (UTC)

 * Apologies for quick revert. You gave no explanations and the reference is indeed present in many sources.

 * Did you see the 1967 paper yourself? If yes, did you read it carefully? May be it is among the passing remarks or trivially follows from some of the remarks, because the idea itself is quite simple to describe. I remember solving it myself at a student olympiad. And indeed, this reference is given in some books in, e.g., cryptography.

 * If you are right, then I would recommend to do the following, it this order (for various reasons, related with works of wikipedia).
 * Write an article about Floyd's algorithm of finding cycles in a directed graph (one of examples in the mentioned 1967 paper)
 * In the current article, mention that a number of sources refer to the 1967 paper. Point out that in fact the paper covears a different kind of cycle finding algorithm, referring to the wikipedia article
 * Mention the Knuth's "unreferenced reference".

 * When I will be in a university library, I will verify the 1967 article myslef. And of course, keep looking for independent confirmation. `'Míkka 15:56, 17 October 2007 (UTC)

 * The 1967 article is available as a pdf at the ULR given above, and contains a description of an application of the algorithm already described in Depth-first search to cycle-finding, although the article is about a way of presenting such an algorithm as a nondeterministic algorithm rather than about dfs.

 * You didn't read my question carefully. I don't doubt it contains what you say. My question was whether it contains anything else: an idea, a hint, a footnote. For a mathematician I'd expect you be more carful with details. What is more, the article is not "available as a pdf". It is "available if you have a subscription or pay for it" Anyway, I did read the article myself after all and hereby confirm that no, I didn't see any even remote hints about the "turtle and hare" trick nor even about detection of a cycle. `'Míkka 22:23, 17 October 2007 (UTC)

 * Sorry! I did read the question: what I did was to omit the word only from my answer. And I was unaware that the pdf wasn't free because an institutional subscription entirely hides the page calling for payment.89.243.59.31 05:59, 18 October 2007 (UTC)

 * I suspect that the Art of Computer Programming is the ultimate source for the presentation in Floyd's cycle-finding algorithm, because it uses the symbols λ and μ for the parameters, although confusingly Knuth uses λ where the article uses μ, and μ where the article has λ.

 * I'll ask Don Knuth whether he knows of an earlier published version of tortoise-and-hare when I see him next.89.243.59.31 20:01, 17 October 2007 (UTC)

 * In the meantime I described the situation in a footnote in the article. Constructive criticism welcome, as always. —David Eppstein 21:14, 17 October 2007 (UTC)

Other algorithms
Floyd's is not the only algorithm for solving the problem of detecting cycles in a sequence or functional graph. There is also an algorithm of Brent: maintain a single pointer into the sequence, and compare it to the sequence value at the last position that was a power of two. An algorithm of Nivasch 10.1016/j.ipl.2004.01.016 that uses more space but fewer function evaluations, and many other people's algorithms described briefly in Nivasch's paper. I don't think we need separate Wikipedia articles for all of these different techniques, but I think it would be appropriate to have an article that covers the subject more generally, describing both the different techniques and several applications of this problem (loop detection in logic programming, Pollard's rho factorization, cycle detection for pseudorandom number generators, etc). So I suggest we move this article to Loop detection or Cycle detection or Cycle-finding algorithms or something more generically named like that and add descriptions of the other techniques. Any thoughts on this plan? —David Eppstein 21:39, 17 October 2007 (UTC)
 * I agree that it would be a good idea to make an article about the problem, rather than about one particular solution. `'Míkka 22:02, 17 October 2007 (UTC)

While I am at this (not for long), I'd like to say that the description of the algorithm has two major flaws IMO. First, the algorithm must be described in terlm of the most basic model, i.e., in terms of a graph. Second, I fail to uderstand why a pseudo-random function is used in description. I don't even want to lookm into "pseudo-random function" article: the phrase "Clearly such a sequence must cycle after at most n iterations of the pseudo-random function, because there are only n possible values for an element." implies that the value of f(i) is deterministic regardless the call of the function. And the whole discussion is in fact valid for any funcions whose range belongs to its domain. Or am I missinig something here? `'Míkka 23:37, 17 October 2007 (UTC)

 * I think the point of the pseudo-random function part is not that it be pseudo-random, but that it be a function. You can't use this algorithm for a sequence that is truly random (because it won't cycle), and using it for sequences that depend on more than just the previous term (such as e.g. Fibonacci modulo p) requires some modification. —David Eppstein 23:46, 17 October 2007 (UTC)

 * The pseudo-random is probably another artefact of the original source for the article being Art of Computer Programming, where the algorithm appears in the context of testing the cycle length of Pseudorandom number generators. (The same is true of Richard Brent's article.) The link redirecting to pseudorandom function family is clearly misleading.89.243.59.31 05:59, 18 October 2007 (UTC)

I've 2 questions ? Can we use floyds cycle finding algorithm sequence of values which repeats itself but contains duplicate values. Fib mod m can have values like 0,1,1,2,3... now hare and tortoise are equal at 1,1 or some other elements. Shouldn't they be unique ? I think we need to find the periodicity using KMP or something alike. Please suggest.

 * There's no unambiguous way of determining a cycle in an infinite sequence that may have repetitions: any time you think you have a repetition, it could change to a longer one. For instance, your sequence could begin
 * 0,1,1,2,3,0,1,1,2,3,0,1,1,2,3,4,0,1,1,2,3,0,1,1,2,3,0,1,1,2,3,4,0,1,1,2,3,0,1,1,2,3,0,1,1,2,3,4,5,...
 * KMP would work to find repetitions in finite strings where the whole sequence is known (or to find the repetitions up to a given point in an infinite sequence), as you suggest, but would use far greater amounts of memory than the algorithms described here. —David Eppstein (talk) 15:37, 27 February 2009 (UTC)

How is such algorithm called — early loop detection in OpenRC? I think it should be added to the article. —Xaionaro (talk) 11:20, 24 January 2014 (UTC)

Too much graphical-heavy image
The hare - tortoise image is cute, but I think it's too much 'heavy'. A more stylized and lighter image may be better. —Preceding unsigned comment added by 79.42.205.63 (talk • contribs)

I like it.--CzarKirk (talk) 03:30, 16 January 2009 (UTC)

Example code needs fixing
Currently both the floyd and brent code examples of the algorithm leaves out a critical component, making it nearly useless as is. both algorithms have an undefined function f(someNode) which is explained to simply return the node next to someNode. However in most graphs there isnt a single node adjacent to another, there are several. since f isnt actually defined it doesnt tell you which of the neighbor nodes should be selected, and clearly just picking any at all wont work (or else the entire graph doesnt get traversed). This should be fixed, or perhaps someone could explain this to me and i can fix it? - Debeo Morium: to be morally bound (Talk | Contribs) 04:55, 21 April 2010 (UTC)
 * You seem to have mistaken this for an article about finding cycles in arbitrary graphs. For that, you probably want depth first search or something like that. This is about finding cycles in sequences defined by repeatedly calling a function. f is an input to the algorithm, and (together with the initial value) defines the sequence in which a cycle is to be found. —David Eppstein (talk) 05:06, 21 April 2010 (UTC)

Cycle detection in computer science
In computer science, cycle detection is the problem of detecting whether a Graph has any paths that begin and end in the same vertex. I think there should be a subsection about this, or a link to another page that talks about this problem. --Erel Segal (talk) 10:09, 3 January 2011 (UTC)
 * I think the "in mathematics" of our existing lede is inaccurate: the subject of the current article is computer science, just as the different subject you discuss is. If you think cycle detection in graphs is notable enough for its own article, you're welcome to write cycle detection (graph theory) and we can add a hatnote linking to it from this one. —David Eppstein (talk) 17:36, 3 January 2011 (UTC)

 * I’m thinking of starting a section under something like Cycle (graph theory). Vadmium (talk) 10:45, 13 September 2011 (UTC).
 * Please see WP:NOTDICT. If it's not about the same problem, it should not be in the same article. —David Eppstein (talk) 15:39, 13 September 2011 (UTC)

 * Can you elaborate? Are you saying that and  are not closely enough related to the topic of Cycle (graph theory) to be mentioned in that article? My main problem was that there is bugger-all information relating cycles in directed graphs to things like topological sorting, strongly connected components, back edges. See also Talk:Cycle (graph theory). Vadmium (talk) 02:00, 14 September 2011 (UTC).
 * Yes. I believe that the problem of finding cycles in a function or sequence (what this article is about) is very different from the problem of finding cycles in a digraph (what you seem to be talking about). They are different problems with different types of inputs, different types of outputs, different styles of analysis, and different algorithms used to solve them. I believe that it would be more confusing than helpful to conflate them. With a function or sequence input over a finite domain, one knows that cycles are always going to exist, there is a unique cycle that can be reached from any starting value, and the goal is to find that cycle using time and space much smaller than the domain of the function. The input is not a graph; it is a single starting value together with a black box for generating the value of a function. Instead, for finding cycles in digraphs, one does not generally know whether or not cycles exist, the whole digraph is given as input so there's no point in spending less than linear time, there are multiple different outgoing edges from each vertex, there can in generally be exponentially cycles, and there's no clear definition of "the cycle" that you want to find. I think you would be much better off discussing the cycle finding problem for digraphs in connection with either topological sorting or strongly connected components — a digraph either has a topological sort or a cycle, so finding a cycle when topological sorting fails can be a useful sanity check, and the strongly connected components are exactly the sets of vertices that are part of a (not necessarily simple) cycle. —David Eppstein (talk) 04:09, 14 September 2011 (UTC)

 * Okay, thanks for explaining. I think I misunderstood and perhaps my original comment wasn’t clear. I meant to suggest that another existing article, Cycle (graph theory), should be the place for this graph theory problem. The reason it’s all over this talk page of the iterated functions article is probably because the title Cycle detection is ambiguous without further explanation, and some graph theory pages link to it.
 * Anyway, I’ve created my section (in a different article) and added a hatnote for it. Vadmium (talk) 06:06, 14 September 2011 (UTC).
 * Oh, ok. Sorry for misunderstanding your intentions. Yes, the graph theoretic cycle article seems like a good place to at least mention this topic. —David Eppstein (talk) 06:10, 14 September 2011 (UTC)

Cycle detection in directed graphs
I agree with Erel Segal. I think this article, "cycle detection", should define cycle detection as the more general detection of cycles in a directed graph. The special case dealt with here (functional case, where a given node/value has a single successor) deserves special attention, but as a special case, not as the full "cycle detection" problem.

I was searching for incremental algorithms for the graph theoretic cycle detection -- i.e., where you've identified all cycles in a huge network, then one link is changed and you need to adjust the cycle identification. Is it possible to do this more efficiently than a full reprocessing of the full network? I don't know the answer (yet), but it would have been nice for me if the article might have addressed this. — Preceding unsigned comment added by Ldc (talk • contribs) 22:29, 10 August 2011 (UTC)

Any speeds of Hare and Tortoise?
Does it have to be 1x and 2x or any numbers will do? Should the numbers not be co-prime? What about 2x and 8x or 21x and 55x? 117.198.122.24 (talk) 07:38, 26 October 2012 (UTC)

 * They need to be coprime, and the larger they are the more steps you might have to take until finding the loop. So 1 and 2 are the best choice. —David Eppstein (talk) 15:14, 26 October 2012 (UTC)

 * Why co-prime? What difference does it make? 117.198.124.222 (talk) 06:38, 28 October 2012 (UTC)

 * I'd like to note, for any future reader of this discussion, that the respective speeds of tortoise and hare don't need to be coprime; they only need to be non-zero and distinct. Let $$s_T, s_H \in \mathbb{N}, \mathrm{s.t.}\ s_T \le s_H,$$ denote the speeds of the tortoise and hare respectively; let $$\Delta = s_H-s_T$$. To find a solution for any $$\mu \geq 0$$ and $$\lambda > 0$$, the necessary condition imposed on $$s_T$$ and $$s_H$$ is that there exist $$k, l \in \mathbb{N^{+}}$$, such that (a) $$k \cdot \Delta = l \cdot \lambda$$, and (b) $$k \cdot s_T \geq \mu$$.

 * The reasoning is this: 1. In each step, the mutual distance of tortoise and hare increases by the difference of their speeds $\Delta$, so after $k$ steps, their distance is $k \cdot \Delta$. We want this distance to be a positive multiple of $\lambda$: if their distance is a positive multiple of $\lambda$ and they both have the same value, we've found the cycle. It's necessary to note that the multiple must be positive and not zero, because if it's zero, they are at the same position in the sequence and thus always have the same value. In such case, we obviously cannot find a cycle. This is why we must require that both $k$ and $\Delta$ are non-zero; the latter implying that $s_T$ and $s_H$ are distinct. From here on, assume $\Delta \neq 0$.

2. We must assure that after the $k^\mathrm{th}$ step, both tortoise and hare are inside the cycle. Hence the requirement $k \cdot s_T \geq \mu$, which ensures that after the $k^\mathrm{th}$ step, the tortoise (and thus the hare as well) has entered the cycle. Note that $k$ can be any positive natural number, and therefore any positive multiple of $\lambda$; let $k_\lambda$ denote any such positive multiple of $\lambda$. For each $k_\lambda$, $k_\lambda \cdot \Delta$ is also a positive multiple of $\lambda$, viz. $\exist l \in \mathbb{N^{+}}: k_\lambda \cdot \Delta = l \cdot \lambda$. In other words, any $k_\lambda$ can satisfy equation (a). Now let's assume $s_T = 0$; then the equation (b) $k_\lambda \cdot s_T \geq \mu$ implies $\mu = 0$. But since we want to allow any $\mu \geq 0$, we must require $s_T \ne 0$ and thus, since $s_T$ cannot be negative, $s_T > 0$. There are infinitely many $k_\lambda$, and assuming $s_T > 0$, there are also infinitely many those $k_\lambda$, for which $k_\lambda \cdot s_T \geq \mu$. In other words, if the tortoise is moving at a non-zero speed, it would eventually enter the cycle and synchronize with the hare, no matter how large $\mu$ or $\lambda$ or $s_H$ is.
 * undefined

 * We can pick any $$s_T$$ and $$s_H$$, as long as they fulfill the above conditions, namely $$s_T \ne s_H$$ and $$s_T > 0$$, or simply $$0 < s_T < s_H$$. Whether they are coprime or not does not matter. --84.245.121.75 (talk) 09:17, 3 August 2020 (UTC)

Where do the Hare and Tortoise meet?
I can't seem to understand why the T and H should meet at the node, k nodes before entry point, whenever the length of the list excluding (before) the loop is k? Does this only work when the speeds are x and 2x or all the time? 117.198.124.222 (talk) 06:39, 28 October 2012 (UTC)
 * At each step the hare gets one position farther ahead of the tortoise, because it is faster by one unit. So after k steps (when the tortoise enters the loop) the hare is k positions ahead, or equivalently L-k steps positions behind, where L is the length of the loop. And after L-k more steps, the hare has caught up to the tortoise again. At this time the tortoise will have moved L-k units past where it entered the loop; that is, k nodes before the entry point.—David Eppstein (talk) 07:19, 28 October 2012 (UTC)
 * What if the speed of the tortoise and hare are x and y respectively? and the nodes before the loop is k and nodes in the loop is L?117.198.136.11 (talk) 06:30, 30 October 2012 (UTC)

Wrong equation
x_i = x_i + kλ cannot be true unless kλ=0. I assume it's supposed to be x_(i+1) = x_i + kλ — Preceding unsigned comment added by 208.54.80.171 (talk) 23:31, 9 December 2012 (UTC)
 * Yes, that is the wrong equation. It is so wrong that it is not even in the article. Instead, what we have is x_i = x_{i+kλ}, which is not so difficult to satisfy. —David Eppstein (talk) 23:37, 9 December 2012 (UTC)

Mistake in Python floyd code
It seems like the second loop might never end. Both Tortoise and Hare advance at the same speed. What's going on there? — Preceding unsigned comment added by 31.154.17.58 (talk) 14:28, 8 May 2016 (UTC)
 * Try working through a few examples. —David Eppstein (talk) 17:57, 8 May 2016 (UTC)
 * I tried to run an example with the following directed graph: 0 -> 1 -> 2 -> 3 -> 1. Here: λ = 3 and μ = 1.
 * Existing the first while loop, I have parameters power=2, lam=1.
 * This means that after the for loop with range(lam), the distance between hare and tortoise is 2, and not λ = 3.
 * Link to an image of the execution I wrote using my iPad: https://www.dropbox.com/s/gv28mk695pjig8b/execution-python-code-brent-algorithm-section-1.png?dl=0
 * I cannot find the mistake in my execution. Are you sure the algorithm is correct? M12ats 87 (talk) 13:04, 20 July 2022 (UTC)

Mistake in Brent's article
LCG of TI calculators is ok, because they have more than 32 bits of precision, Brent hit integer overflow in his own program rather than mistake in LCG — Preceding unsigned comment added by 94.244.46.42 (talk) 12:16, 14 February 2021 (UTC)

Mistake in Python floyd code 2
I tried to run an example ([1]) with the following directed graph: 0 → 1 → 2 → 3 → 1. Here: λ = 3 and μ = 1.

Exiting the first while loop, I have parameters power=2, lam=1. This means that after the for loop with range(lam), the distance between hare and tortoise is 2, and not λ = 3.

I cannot find the mistake in my execution. Are you sure the algorithm is correct?

Resources:

[1] Link to an image of the execution I wrote using my iPad: https://www.dropbox.com/s/gv28mk695pjig8b/execution-python-code-brent-algorithm-section-1.png?dl=0

M12ats 87 (talk) 21:45, 10 August 2022 (UTC)

 * I found my mistake:
 * In an iteration where lam (which stands for lambda, i.e., λ) is zeroed, we still do lam += 1 at the end of the iteration. Thus, we never have lam = 0 at the end of an iteration.
 * With that in mind, illustration 2 in my execution image shows the states of variables after the first iteration, and I have lam = 0. This is wrong. After fixing this, the execution is okay, and we get the correct parameters.
 * Two more points:
 * 1. The headline for my question is incorrect: My illustration represents an execution of Brent's algorithm, not Floyd's, because only Brent's algorithm has a variable named power.
 * 2. The illustration I used is confusing. Using a table where each row represents variable state after an iteration and columns represent variable states is more comfortable. For positions of pointers, I flat the linked list and also put it in a column. Example: https://www.dropbox.com/s/ni5s3j9keuleqai/execution-python-code-brent-algorithm_version2_trimmed.png?dl=0 M12ats 87 (talk) 13:58, 21 October 2022 (UTC)

Possible typo in code comment
In code we can see Because the # distance between them is constant at 2ν, a multiple of λ, # they will agree as soon as the tortoise reaches index μ.

What is 2ν? Is it node "ν", where there two in-edge, or something else? Tookser (talk) 10:50, 24 March 2024 (UTC)

title: Talk:Cycle detection